func_code_string: #include <bits/stdc++.h>   using namespace std;   long long M;   const int N_MAX = 2;   template <class T>   void mul(int n, const T A[N_MAX][N_MAX], const T x[N_MAX], T y[N_MAX]) {     static T z[N_MAX];     for (int i = 0; i < (n); i++) {       z[i] = 0;       for (int j = 0; j < (n); j++) z[i] = (z[i] + A[i][j] * x[j]) % M;     }     for (int i = 0; i < (n); i++) y[i] = z[i];   }   template <class T>   void mul(int n, const T A[N_MAX][N_MAX], const T B[N_MAX][N_MAX],            T C[N_MAX][N_MAX]) {     static T tmp[N_MAX][N_MAX];     for (int i = 0; i < (n); i++)       for (int j = 0; j < (n); j++) {         tmp[i][j] = 0;         for (int k = 0; k < (n); k++)           tmp[i][j] = (tmp[i][j] + A[i][k] * B[k][j]) % M;       }     for (int i = 0; i < (n); i++)       for (int j = 0; j < (n); j++) C[i][j] = tmp[i][j];   }   template <class T>   void pow(int n, const T A[N_MAX][N_MAX], long long m, T B[N_MAX][N_MAX]) {     static T tmp[N_MAX][N_MAX];     for (int i = 0; i < (n); i++)       for (int j = 0; j < (n); j++) {         tmp[i][j] = A[i][j];         B[i][j] = (i == j ? 1 : 0);       }     for (int t = 0; m > 0; t++) {       if (m & (1LL << t)) {         mul(n, B, tmp, B);         m -= 1LL << t;       }       mul(n, tmp, tmp, tmp);     }   }   long long fib(long long n) {     long long A[2][2] = {{1, 1}, {1, 0}}, x[2] = {1, 0};     pow(2, A, n - 1, A);     mul(2, A, x, x);     return x[0];   }   int main() {     long long l, r, k;     cin >> M >> l >> r >> k;     vector<long long> cand;     for (long long i = 1; i * i <= r; i++) {       cand.push_back(i);       for (int j = -1; j <= 1; j++) {         cand.push_back(l / i + j);         cand.push_back(r / i + j);       }     }     long long idx = 1;     for (int i = 0; i < (cand.size()); i++) {       long long a = cand[i];       if (a > 0 && r / a - (l - 1) / a >= k) idx = max(idx, a);     }     cout << fib(idx) << endl;     return 0;   }   