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



int a[100010];
int N,S,W,Q;
int special(int m){
	int c[5] = {};
	int ans = 0;
	for(int i = 0 ; i < N ; i++){
		c[a[i]%m]++;
		if( a[i] != 0 ){
			ans += c[0];
		}
	}
	return ans;
}
int main(){
	while( cin >> N >> S >> W >> Q && 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; }
		}
		reverse(a,a+N);
		if( Q == 2 || Q == 5 ){
			cout << special(Q) << endl;
		}else{
			
			map<int,int> d;
			d[0] = 1;
			int now = 0;
			int ans = 0;
			int ten = 1;
			for(int i = 0 ; i < N ; i++){
				now = (now+1ll*a[i]*ten%Q) % Q;
				if( a[i] != 0 ){
					ans += d[now];
				}
				d[now]++;
				ten *= 10;
				ten %= Q;
			}
			cout << ans << endl;
		}
		
		
	}
}