You are given a sequence a0a1...aN-1 digits and a prime number Q. For each i ≤ j with ai ≠ 0, the subsequence aiai+1...aj can be read as a decimal representation of a positive integer. Subsequences with leading zeros are not considered. Your task is to count the number of pairs (i, j) such that the corresponding subsequence is a multiple of Q.



Input

The input consists of at most 50 datasets. Each dataset is represented by a line containing four integers N, S, W, and Q, separated by spaces, where 1 ≤ N ≤ 105, 1 ≤ S ≤ 109, 1 ≤ W ≤ 109, and Q is a prime number less than 108. The sequence a0...aN-1 of length N is generated by the following code, in which ai is written as a[i].


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; }
}


Note: the operators /, %, and ^ are the integer division, the modulo, and the bitwise exclusiveor, respectively. The above code is meant to be a random number generator. The intended solution does not rely on the way how the sequence is generated.

The end of the input is indicated by a line containing four zeros separated by spaces.

Output

For each dataset, output the answer in a line. You may assume that the answer is less than 230.

Example

Input

3 32 64 7
4 35 89 5
5 555 442 3
5 777 465 11
100000 666 701622763 65537
0 0 0 0


Output

2
4
6
3
68530
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
//const ll mod = 1000000007;
ll N, S, W, Q;
ll mod;
ll ten[200001];
ll inv[200001];
ll beki(ll a, ll b, ll mod = Q) {
    if(b == 0) return 1;
    ll ret = beki(a, b / 2, mod);
    ret = ret * ret % mod;
    if(b & 1) ret = ret * a % mod;
    return ret;
}
vector<ll> a;

void generator() {
    a.resize(N);
    ll 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;
    }
}

ll f(ll l, ll r) {
    if(l == r) return 0;
    if(r == l + 1) {
        //cerr << "one: " << l << " "<< (a[l] % Q == 0) << endl;
        return (a[l] % Q == 0) && (a[l] != 0);
    }
    ll ans = 0;
    ll mid = (l + r) / 2;
    map<ll, ll> mp;
    ll now = 0;
    ll Total = 0;
    for(int i = mid - 1; i >= l; i--) {
        now += beki(10, i - mid + 1) * a[i];
        now %= mod;
        //cerr << i << " " << now << endl;
        if(a[i] != 0) {
            mp[now]++;
            Total++;
            //cerr << i << " " << now << endl;
        }
    }
    now = 0;
    for(int i = mid; i < r; i++) {
        now *= 10;
        now += a[i];
        now %= mod;
        if(10 % Q != 0) {
            ll tmp = Q - now;
            tmp %= mod;
            //ll tmp2 = ten[i + 1 - mid];
            tmp *= inv[i+1-mid];
            tmp %= mod;
            //cerr << i << " " << now << " " << tmp << " " << mp[tmp] << endl;
            ans += mp[tmp];
        } else {
            if(now % Q == 0) {
                ans += Total;
            }
        }
    }
    //cerr << "sum: " << l << " " << mid << " " << r << " " << ans << endl;
    return ans + f(l, mid) + f(mid, r);
}

void solve() {
    generator();
    for(ll i = 1; i <= 2e5; i++) {
        ten[i] = ten[i-1] * 10 % mod;
        //inv[i] = beki(ten[i], mod - 2);
    }
    inv[200000] = beki(ten[200000], mod - 2);
    for(ll i = 2e5 - 1; i >= 0; i--) {
        inv[i] = inv[i+1] * 10 % mod;
    }
    /*
    for(int i = 0; i < N; i++) cerr << a[i] << " ";
    cerr << endl;
    */
    cout << f(0, N) << endl;
}

int main() {
    //cout.precision(10);
    ten[0] = 1;
    inv[0] = 1;
    while(cin >> N >> S >> W >> Q) {
        mod = Q;
        if(N == 0) break;
        solve();
    }
    return 0;
}
