#include <iostream>
#include <algorithm> 
//nicely trolled hackerrank..well done..u alomost destroyed my PC
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    unsigned long long n, s, p, q;
    std::cin >> n >> s >> p >> q;
    if (n == 0) {
        std::cout << 0 << std::endl;
        return 0;
    }
    if (p == 0) {
        unsigned long long a_1 = q;
        if (s == a_1) std::cout << 1 << std::endl;
        else std::cout << std::min(n, 2ULL) << std::endl;
        return 0;
    }
    if (p == 1 && q == 0) {
        std::cout << 1 << std::endl;
        return 0;
    }
    const unsigned long long MASK = (1ULL << 31) - 1;
    unsigned long long tortoise = s;
    unsigned long long hare = s;
    bool cycle_found = false;
    for (unsigned long long i = 0; i < n; ++i) {
        tortoise = (tortoise * p + q) & MASK;
        hare = (hare * p + q) & MASK;
        hare = (hare * p + q) & MASK;
        if (tortoise == hare) {
            cycle_found = true;
            break;
        }
    }
    if (!cycle_found) {
        std::cout << n << std::endl;
        return 0;
    }
    unsigned long long mu = 0;
    tortoise = s;
    while (tortoise != hare) {
        tortoise = (tortoise * p + q) & MASK;
        hare = (hare * p + q) & MASK;
        mu++;
    }
    unsigned long long lambda = 1;
    tortoise = (tortoise * p + q) & MASK;
    while (tortoise != hare) {
        tortoise = (tortoise * p + q) & MASK;
        lambda++;
    }
    std::cout << std::min(n, mu + lambda) << std::endl;

    return 0;
}