// SmartCoder
#include <bits/stdc++.h>

using namespace std;

#define sz(a) int((a).size())

#define MAXN 1000007
#define MOD 1000000007

typedef long long ll;
const double eps = 1e-11;

ll add(ll x, ll y) {
	x += y;
	return x >= MOD ? x - MOD : x;
}
int N;
ll memo[MAXN][3];
ll rec(int cur, int prev) {
	if (cur == N) return 1ll;
	if (cur > N) return 0;
	ll res = 0;
	ll &re = memo[cur][prev];
	if (re != -1) return re;
	if (prev == 1) {
		res = add(res, rec(cur + 1, 1));
		res = add(res, rec(cur + 2, 2));
	}
	if (prev == 2) {
		res = add(res, rec(cur + 1, 1));
	}
	return re = res;
}
class HopscotchCounting {
       public:
	int count(int _N) {
		N = _N;
		memset(memo, -1, sizeof(memo));
		return (int)rec(0, 1);
	}
};

public int[] getLongest(int n, int seed, int t, int s, int f)
    {
        long h[]=new long[n];
        h[0] = (seed * 1103515245l + 12345) % (1l<<31);
        for (int i = 1;i<n;i++) h[i] = (h[i-1] * 1103515245l + 12345) % (1l<<31);
        HashMap<Long,Integer> ha=new HashMap<>();
        int ss=0;
        int ff=0;
        ha.put(0l,-1);
        int m=0;
        int a=0;
        int b=0;
        long c=1l*s*n+f;
        for(int x=0;x<n;x++)
        {
            if(h[x]>t)ss++;
            else ff++;
            long v=1l*ss*n+ff;
            if(ha.containsKey(v%c))
            {
                int i=ha.get(v%c);
                int d=x-i;
                if(d>m)
                {
                    m=d;
                    a=i+1;
                    b=x+1;
                }
            }
            if(!ha.containsKey(v%c))ha.put(v%c,x);
        }
        return new int[]{a,b};
    }