#include<map>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100000

using namespace std;
map<int,int>m;
int a[MAXN+80],n,q;
int chk()
{
	int i,ans=0,appear0=0;
	for(i=1;i<=n;i++)
	{
		if(a[i]==0)
			appear0++;
		if(a[i]%q==0)
			ans+=i-appear0;
	}
	return ans;
}
int check()
{
	m.clear();
	m[0]=1;
	int houS=0,i,ans=0,pow10=1;
	for(i=n;i;i--)
	{
		houS=(houS+a[i]*pow10)%q;
		if(a[i])
			ans+=m[houS];
		m[houS]++;
		pow10=pow10*10%q;
	}
	return ans;
}
int main()
{
	int s,w,g,i;
	while(scanf("%d%d%d%d",&n,&s,&w,&q)==4&&(n||s||w||q))
	{
		g=s;
		for(i=1;i<=n;i++)
		{
			a[i]=(g/7)%10;
			if(g&1)
				g=(g>>1)^w;
			else
				g>>=1;
		}
		if(q==2||q==5)
			printf("%d",chk());
		else
			printf("%d",check());
		putchar('\n');
	}
	return 0;
}