//07
#include<iostream>
#include<map>

using namespace std;

int main(){
  for(int n,s,w,q;cin>>n>>s>>w>>q,n|s|w|q;){
    int g=s;
    int a[100000];
    for(int i=0;i<n;i++){
      a[i]=g/7%10;
      g=g/2^(g%2?w:0);
    }
    int ans=0;
    if(q==2||q==5){
      int ac=0;
      for(int i=0;i<n;i++){
	ac+=a[i]!=0;
	if(a[i]%q==0){
	  ans+=ac;
	}
      }
    }else{
      map<int,int> m;
      m[0]=1;
      long long r=1;
      int c=0;
      for(int i=n-1;i>=0;i--){
	c=(c+r*a[i])%q;
	if(a[i]){
	  ans+=m[c];
	}
	m[c]++;
	r=(r*10)%q;
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}