recc

#include <bits/stdc++.h>

#define ll long long
#define Bmax 1005

using namespace std;

ifstream fin("recc.in");
ofstream fout("recc.out");

struct mat
{
    int M[4][4];
};
mat Z;

ll N;
int L;
int B, X, K;
int A[4];
int vals[Bmax * Bmax];
int cnt[Bmax * Bmax];

mat mult(mat A, mat B)
{
    mat C;
    memset(C.M, 0, sizeof(C.M));
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            for(int k = 0; k < 4; k++)
                C.M[i][j] = (C.M[i][j] + 1ll * A.M[i][k] * B.M[k][j]) % K;
    return C;
}

mat pw(mat A, ll N)
{
    if(N == 1)
        return A;
    if(N % 2 == 1)
        return mult(A, pw(A, N - 1));
    mat P = pw(A, N / 2);
    return mult(P, P);
}

ll ans;

int freq(int v)
{
    for(int le = 1, ri = L; le <= ri;)
    {
        int mid = (le + ri) / 2;
        if(vals[mid] == v)
            return cnt[mid];
        if(vals[mid] < v)
            le = mid + 1;
        else
            ri = mid - 1;
    }
    return 0;
}

int main()
{
    fin >> N >> B >> X >> K;
    for(int i = 0; i < 4; i++)
        fin >> A[i], Z.M[3 - i][3] = A[i] % K;
    for(int i = 0; i < 3; i++)
        Z.M[i + 1][i] = 1;
    Z = pw(Z, N - 4);
    for(int i = 0; i < 4; i++)
        A[i] = Z.M[i][3];
    L = 0;
    for(int i = 1; i <= B; i++)
        for(int j = 1; j <= B; j++)
        {
            int v = (1ll * A[0] * i % K + 1ll * A[1] * j % K) % K;
            vals[++L] = v;
        }
    sort(vals + 1, vals + L + 1);
    int newL = 1;
    cnt[1] = 1;
    for(int i = 2; i <= L; i++)
        if(vals[newL] != vals[i])
            vals[++newL] = vals[i], cnt[newL] = 1;
        else
            cnt[newL]++;
    L = newL;
    ll ans = 0;
    for(int i = 1; i <= B; i++)
        for(int j = 1; j <= B; j++)
        {
            int v = (1ll * A[2] * i % K + 1ll * A[3] * j % K) % K;
            v = (X - v + K) % K;
            ans += freq(v);
        }
    fout << ans << "\n";
    return 0;
}