#include<bits/stdc++.h>
using namespace std;
#define int long long
int extgcd(int a,int b,int& x,int& y){
  int d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
int mod_inverse(int a,int m){
  int x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}
int mod_pow(int x,int n,int mod){
  int res=1;
  while(n>0){
    if(n&1) (res*=x)%=mod;
    (x*=x)%=mod;
    n>>=1;
  }
  return res;
}
int a[114514],b[114514],c[114514],r[114514];
signed main(){
  int n,s,w,q;
  while(cin>>n>>s>>w>>q,n){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    memset(r,0,sizeof(r));
    int g=s;
    for(int i=0;i<n;i++){
      a[i+1]=(g/7)%10;
      if(g%2==0) g=(g/2);
      else g=(g/2)^w;
    }
    if(q==2||q==5){
      int ans=0,cnt=0;
      for(int i=0;i<n;i++){
	if(a[i+1]) cnt++;
	if(a[i+1]%q==0) ans+=cnt;
      }
      cout<<ans<<endl;
      continue;
    }
    for(int i=0;i<n;i++)
      b[i+1]=(b[i]*10+a[i+1])%q;
    map<int,int> m;
    m[0]=1;
    r[0]=1;
    for(int i=0;i<n;i++){
      r[i+1]=(r[i]*mod_inverse(10,q))%q;
      c[i+1]=(b[i+1]*r[i+1])%q;
      m[c[i+1]]++;
    }
    int ans=0;
    for(int i=0;i<n;i++){
      m[c[i]]--;
      if(!a[i+1]) continue;
      ans+=m[(b[i]*r[i])%q];
    }
    cout<<ans<<endl;
  }
  return 0;
}