#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[100010];
int N, S, W, Q;

int main(){
    while(cin >> N >> S >> W >> Q && N){
        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 ans = 0;
        if(Q != 2 && Q != 5){
            map<int,int> m = {{0,1}};
            ll dig = 1, cur = 0;
            for(int i = N-1; i >= 0; --i) {
                cur = i == N-1 ? a[i] % Q : cur + a[i]*dig;
                cur %= Q;
                if(a[i] != 0) ans += m[cur];
                m[cur]++;
                dig *= 10;
                dig %= Q;
            }
        } else if(Q == 2 || Q == 5){
            int pos = 0;
            for(int i = 0; i < N; ++i){
                if(a[i] != 0) ++pos;
                if(a[i] % Q == 0) ans += pos;
            }
        } 
        cout << ans << endl;
    }
}