import std.stdio;
import std.ascii;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

int[] Gen(int S, int N, int W) {
    auto a = new int[N];
    int g = S;
    for(int i=0; i<N; i++) {
        a[i] = (g/7) % 10;
        if( g%2 == 0 ) { g = (g/2); }
        else           { g = (g/2) ^ W; }
    }
    return a;
}

int len(int x) {
    return cast(int)x.to!string.length;
}

long _C(int n, int r) {
    alias memoize!_C C;
    if (n < r) return 0;
    if (r == 1) return n;
    if (n == r) return 1;
    return C(n - 1, r - 1) + (n - 1, r);
}
alias memoize!_C C;

void main() {
    int N, Q;
    int[] A;

    long Pow(long x, int n) {
        x %= Q;
        if (n == 0) return 1;
        if (n % 2 == 1) return (x * Pow(x, n - 1)) % Q;
        return Pow((x * x) % Q, n / 2);
    }

    bool input() {
        int S, W;
        scanf("%d %d %d %d\n", &N, &S, &W, &Q);
        if (N == 0 && S == 0 && W == 0 && Q == 0) return false;
        A = Gen(S, N, W);
        return true;
    }
    void solve() {
        reverse(A);
        int[] L = new int[N + 1];
        L[0] = 0;
        foreach (i; 0 .. N) {
            L[i + 1] = L[i] + len(A[i]);
        }
        int[] S = new int[N + 1];
        if (Q == 2 || Q == 5) {
            S[0] = 0;
            foreach (i; 0 .. N) {
                S[i + 1] = A[i] % Q;
            }
        } else {
            S[0] = 0;
            foreach (i; 0 .. N) {
                S[i + 1] = (A[i] * Pow(10, L[i]) + S[i]) % Q;
            }
        }

        long Ans = 0;
        int[int] M;
        foreach_reverse (i; 0 .. N + 1) {
            int x = M.get(S[i], 0);
            Ans += x;
            if (i > 0 && A[i - 1] == 0) {
                // do nothing;
            } else {
                M[ S[i] ] = x + 1;
            }
        }
        writeln(Ans);
    }
    while (input) solve;
}