#include<bits/stdc++.h>
using namespace std;

const int MAXN = 100000;

int N, S, W, Q;
int a[MAXN + 10];
map<int, int> Cnt;

void a_table()  {
    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; }
    }
}

void work() {
    int i, ans = 0, MOD = 0, TEN = 1;

    Cnt.clear();
    Cnt[0] = 1;
    for(i = N - 1; i >= 0; i--)  {
        MOD = (MOD + a[i] * TEN) % Q;
        TEN = TEN * 10 % Q;
        if(a[i] != 0)   {
            ans += Cnt[MOD];
        }
        Cnt[MOD]++;
    }

    cout << ans << endl;
}

int main()  {
    while(scanf("%d%d%d%d", &N, &S, &W, &Q) == 4 && (N || S || W || Q)) {
        a_table();
        if(Q == 5 || Q == 2)
		{
			int ans = 0;
			int cnt = 0;
			for(int i = 0;i < N;i++)
			{
				if(a[i] != 0)cnt++;
				if(a[i] % Q == 0)ans += cnt;
			}
			printf("%d\n",ans);
			continue;
		}
        work();
    }
    return 0;
}