#include <bits/stdc++.h>   using namespace std;   long long m, l, r, k;   struct Matrix {     long long W[2][2];   };   Matrix operator*(const Matrix& A, const Matrix& B) {     Matrix S;     memset(S.W, 0, sizeof(S.W));     for (int i = 0; i < 2; ++i)       for (int j = 0; j < 2; ++j)         for (int l = 0; l < 2; ++l)           S.W[i][j] = (S.W[i][j] + A.W[i][l] * B.W[l][j]) % m;     return S;   }   Matrix operator^(Matrix A, long long e) {     Matrix S;     S.W[0][0] = S.W[1][1] = 1;     S.W[0][1] = S.W[1][0] = 0;     while (e) {       if (e & 1) S = S * A;       A = A * A;       e >>= 1;     }     return S;   }   long long gcd() {     long long s = 1;     for (long long i = 1; i * i <= r; ++i) {       if (r / i - (l - 1) / i >= k && i > s) s = i;       long long e = r / i;       if (i - (l - 1) / e >= k && e > s) s = e;     }     return s;   }   int main() {     cin >> m >> l >> r >> k;     long long n = gcd();     if (n <= 2)       cout << 1 % m << endl;     else {       Matrix D, S;       D.W[0][0] = 0;       D.W[0][1] = D.W[1][0] = D.W[1][1] = 1;       S = D ^ (n - 2);       cout << (S.W[0][1] + S.W[1][1]) % m << endl;     }     return 0;   }   