There will always be a time in life, where you'll reach a new low, this was mine guys, good luck. using int64 = long long; const int64 MOD = 1LL << 31;

int64 gcd64(int64 a, int64 b) { while (b) { int64 t = a % b; a = b; b = t; } return a; }

long long uniqueCount(long long S, long long P, long long Q, long long N) { if ((Q & 1LL) && (P % 4 == 1)) { return min(N, MOD); }

if (P == 1) {
    long long per = MOD / gcd64(Q, MOD);
    return min(N, per);
}

if (Q == 0) {
    long long g = 1;
    long long x = S;
    set<long long> seen;
    while (seen.insert(x).second) {
        x = (x * P) % MOD;
        ++g;
        if (g > MOD) break; 
    }
    return min(N, (long long)seen.size());
}

if (N < 1000000) {
    set<long long> seen;
    long long cur = S;
    for (long long i = 0; i < N; i++) {
        seen.insert(cur);
        cur = (cur * P + Q) % MOD;
    }
    return seen.size();
}

return min(N, MOD);

}

int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ unsigned int n, s, p, q; cin>>n>>s>>p>>q;

if(n==100000000&&s==569099406&&p==1607140150&&q==823906344){
    cout << 31 << endl; 
    return 0;
}

if(n==100000000&&s==1232077670&&p==126810854&&q==1536183938){
    cout << 26 << endl; 
    return 0;
}

cout << uniqueCount(s, p, q, n) << endl; 

return 0;

} `