#include <bits/stdc++.h>
#define int long long
using namespace std;
signed m;
int l,r,k,maxn=-1;
int mod=1e9+7;
int a[1001][1001],b1[1001][1001],ans[1001][1001];
int n;
void qwq2()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int sum=0;
            for(int q=1;q<=n;q++)
            {
                sum+=ans[i][q]*a[q][j];
                sum%=mod;
            }
            b1[i][j]=sum%mod;
        }
        // cout<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            ans[i][j]=b1[i][j];
        }
    }
}
void qwq1()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int sum=0;
            for(int q=1;q<=n;q++)
            {
                sum+=a[i][q]*a[q][j];
                sum%=mod;
            }
            b1[i][j]=sum;
        }
        // cout<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]=b1[i][j];
        }
    }
}
void qwq(int b)
{
// 	int ans=1;
	while(b)
	{
		if(b&1)
		{
			qwq2();
		}
		qwq1();
		b>>=1;
	}
}
signed main()
{
    cin>>m>>l>>r>>k;
    for(int i=1;i<=sqrt(r);i++)
    {
        int x=i,y=r/i;
        int cnt=0;
        int sum=l/x,sum1=r/x;
        int sum2=sum1-sum-1;
        if(l%x==0) sum2++;
        if(r%x==0) sum2++;
        int cnt1=0;
        int sum3=l/y,sum4=r/y;
        int sum5=sum4-sum3-1;
        if(l%y==0) sum5++;
        if(r%y==0) sum5++;
        if(sum2>=k)
        {
            maxn=max(maxn,i);
        }
        if(sum5>=k)
        {
            maxn=max(maxn,r/i);
        }
    }
    if(maxn==1||maxn==2) cout<<1<<endl;
    else 
    {
    	n=2;
    	mod=m;
    	memset(a,0,sizeof(a));
    	a[1][1]=1;
    	a[1][2]=1;
    	a[2][1]=1;
    	a[2][2]=0;
    	for(int i=1;i<=n;i++)
    	{
    	    for(int j=1;j<=n;j++)
    	    {
    	    	ans[i][j]=0;
    	    }
    	    ans[i][i]=1;
    	}
//    	cout<<maxn<<endl;
    	qwq(maxn-1);
    	cout<<ans[1][1]<<endl; 
	}
    return 0;
}