#include <iostream>
#include <fstream>
#include <map>

using namespace std;

int main(){
	int N, S, W, Q;
	static int a[100000];
	ifstream fin("F.in");
	while(fin >> N >> S >> W >> Q, N){
		map<int, int> mp;
		for(int i=0;i<N;i++){
			a[i] = (S/7)%10;
			if(S%2 == 0) S /= 2;
			else         S = (S/2)^W;
		}
		int res = 0, cur = 0, mul = 1, cnt = 0;
		for(int i=N-1;i>=0;i--){
			if(Q == 2 || Q == 5){
				if(a[i]%Q == 0) cnt++;
				if(a[i] != 0) res += cnt;
			} else {
				cur = (a[i]*mul+cur)%Q;
				if(!mp.count(cur)) mp[cur] = 1;
				else               mp[cur]++;
				mul = (10*mul)%Q;
				if(a[i] != 0) res += mp[cur]-(cur!=0);
			}
		}
		cout << res << endl;
	}
}