You are given a sequence *a*_{0}*a*_{1}...*a*_{N-1} digits and a prime number *Q*. For each *i* ≤ *j* with *a _{i}* ≠ 0, the subsequence

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* ≤ 10^{5}, 1 ≤ *S* ≤ 10^{9}, 1 ≤ *W* ≤ 10^{9}, and *Q* is a prime number less than 10^{8}. The sequence *a*_{0}...*a*_{N-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.

For each dataset, output the answer in a line. You may assume that the answer is less than 2^{30}.

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

2 4 6 3 68530

In the first dataset, the sequence is 421. We can find two multiples of *Q* = 7, namely, 42 and 21.

In the second dataset, the sequence is 5052, from which we can find 5, 50, 505, and 5 being the multiples of *Q* = 5. Notice that we don't count 0 or 05 since they are not a valid representation of positive integers. Also notice that we count 5 twice, because it occurs twice in different positions.

In the third and fourth datasets, the sequences are 95073 and 12221, respectively.

Source: ACM International Collegiate Programming Contest
, Asia Regional Tokyo, Tokyo, Japan, 2010-12-12

http://icpc2010.honiden.nii.ac.jp/

http://icpc2010.honiden.nii.ac.jp/