p00889 Find the Multiples
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
```python
from collections import defaultdict

def gen(N, S, W):
    g = S
    for i in range(N):
        yield (g//7) % 10
        if g % 2 == 0:
            g //= 2
        else:
            g = (g//2) ^ W

def solve():
    N, S, W, Q = map(int, input().split())
    if N == 0:
        return False
    bs = list(gen(N, S, W))
    ans = 0
    if Q == 2 or Q == 5:
        cnt = 0
        for i in range(N):
            b = bs[i]
            if b != 0:
                cnt += 1
            if b % Q == 0:
                ans += cnt
    else:
        rev10 = pow(10, Q-2, Q)
        D = defaultdict(int)
        D[0] = 1
        s = 0; v = 1
        first = 1
        for i in range(N):
            b = bs[i]
            if first and b == 0:
                continue
            s = (s + v * b) % Q
            v = v * rev10 % Q
            ans += D[s]
            if i < N-1 and bs[i+1] != 0:
                D[s] += 1
            first = 0
    print(ans)
    return True

while solve():
    ...

```