#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <complex>
#include <cstdio>
#include <vector>
#include <cctype>
#include <string>
#include <ctime>
#include <cmath>
#include <set>
#include <map>

typedef long double LD;
typedef long long LL;

using namespace std;

#define sz(A) (int)(A).size()
#define mp make_pair
#define pb push_back

int m;
vector<LL> dif_pos;

struct matr {
    LL m[2][2];
};

matr operator * (matr a, matr b) {
    matr res;

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++) {
            res.m[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % m;
            }
        }
    return res;
}

matr power(matr m, LL p) {
    if (p == 1)
        return m;
    if (p % 2)
        return m * power(m, p - 1);
    return power(m * m, p / 2);
}

int fib(LL num) {
    if (num == 1)
        return 1;
    matr f;
    f.m[0][0] = 0;
    f.m[0][1] = f.m[1][0] = f.m[1][1] = 1;
    f = power(f, num);
    return f.m[0][1];
}

int main() {
    LL l, r, k;

    cin >> m >> l >> r >> k;

    if(m == 1){
        cout << 0 << endl;
        exit(0);
    }


    for (LL d = 1; d * d <= r; d++) {
        LL d2 = r / d;
        dif_pos.pb(d);
        dif_pos.pb(d2);
    }

    for (LL d = 1; d * d <= l; d++) {
        if (l % d == 0)
            dif_pos.pb(l / d);
        else {
            if (d) {
                dif_pos.pb(l / (d - 1));
            }
        }
    }

    LL ans = 0;

    for (int i = 0; i < sz(dif_pos); i++) {
        LL d_b = l / dif_pos[i] + LL(l % dif_pos[i] != 0);
        LL u_b = r / dif_pos[i];
        if (u_b - d_b + 1 >= k)
            ans = max(ans, dif_pos[i]);
    }
    cout << fib(ans) << endl;

    return 0;
}