#include<map>
#include<cstdio>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	for(int n,S,W,Q;scanf("%d%d%d%d",&n,&S,&W,&Q),n;){
		static int a[100000];
		int g=S;
		rep(i,n){
			a[i]=(g/7)%10;
			if(g%2==0) g=(g/2);
			else       g=(g/2)^W;
		}

		int ans=0;
		if(Q<10){
			// dp[i+1][j] := ( a[i] を右端とする部分文字列で, 十進整数として見たときに mod Q == j となるものの個数 )
			static int dp[100001][10];
			rep(i,n+1) rep(j,Q) dp[i][j]=0;
			rep(i,n){
				if(a[i]!=0) dp[i+1][a[i]%Q]++;
				rep(j,Q) dp[i+1][(j*10+a[i])%Q]+=dp[i][j];
				ans+=dp[i+1][0];
			}
		}
		else{
			map<int,int> f;
			int sum=0,ten=1;
			for(int i=n-1;i>=0;i--){
				sum=(a[i]*ten+sum)%Q;
				if(a[i]!=0) f[sum]++;
				ten=ten*10%Q;
			}
			sum=0; ten=1;
			int tar=0;
			for(int i=n-1;i>=0;i--){
				ans+=f[tar];
				sum=(a[i]*ten+sum)%Q;
				if(a[i]!=0) f[sum]--;
				tar=(a[i]*ten+tar)%Q;
				ten=ten*10%Q;
			}
		}
		printf("%d\n",ans);
	}

	return 0;
}