#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int n, s, w, q;
int a[100000];
void generate(){
  int g = s;
  for(int i=0;i<n;i++){
    a[i] = (g/7) % 10;
    if(g % 2 == 0) g = (g/2);
    else g = (g/2) ^ w;
  }
}

int calc(){
  int res = 0;
  map<int, int> cnt;
  int val = a[n-1] % q;
  int ten = 1;
  cnt[0]++;
  cnt[val]++;
  if(val == 0 && a[n-1] != 0) res++;
  for(int i=n-2;i>=0;i--){
    ten = (ten * 10) % q;    
    val = (val + a[i] * ten) % q;
    if(a[i] != 0 && cnt.count(val)) res += cnt[val];
    cnt[val]++;
  }
  return res;
}

int calc2(int k){
  int cnt = 0, res = 0;
  for(int i=n-1;i>=0;i--){
    if(k == 2 && a[i] % 2 == 0) cnt++;
    if(k == 5 && (a[i] == 0 || a[i] == 5)) cnt++;
    if(a[i] != 0) res += cnt;
  }
  return res;
}

int main(){
  while(cin >> n >> s >> w >> q && (n|s|w|q)){
    generate();
    if(q == 2 || q == 5) cout << calc2(q) << endl;
    else cout << calc() << endl;
  }
}