#include <bits/stdc++.h>
#define int long long
using namespace std;
int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}
int a[1919810],cnt=0;
int m,l,r,k,cnt1=0,maxn=-1;
void dfs(int x,int cnt2,int gcdx)
{
    if(cnt2>k)
    {
        return;
    }
    if(x>cnt)
    {
        if(cnt2==k)
        {
            maxn=max(maxn,gcdx);
        }
        return;
    }
    if(gcdx==-1)
    {
        dfs(x+1,cnt2+1,x);
        dfs(x+1,cnt2,-1);
    }
    else
    {
        dfs(x+1,cnt2+1,gcd(gcdx,x));
        dfs(x+1,cnt2,gcdx);
    }
}
signed main()
{
    cin>>m>>l>>r>>k;
    cnt=2;
    a[1]=a[2]=1;
    while(a[cnt]<=r)
    {
        a[++cnt]=a[cnt-1]+a[cnt-2];
        if(a[cnt]>=l&&cnt1==0) cnt1=cnt;
    }
    cnt--;
    dfs(cnt1,0,-1);
    cout<<maxn%m;
    return 0;
}

样例

10 1 8 2