Find the Multiples

You are given a sequence of digits $a_0 a_1 \cdots a_{N-1}$ and a prime number $Q$. For every pair of indices $i \le j$ with $a_i \ne 0$, the subsequence $a_i a_{i+1} \cdots a_j$ can be read as the decimal representation of a positive integer. Subsequences with a leading zero (that is, with $a_i = 0$) are not considered. Your task is to count the number of pairs $(i, j)$ for which the corresponding integer is a multiple of $Q$.

The input consists of at most $50$ datasets. Each dataset is a single line with four integers $N$, $S$, $W$, and $Q$ separated by spaces, where $1 \le N \le 10^5$, $1 \le S \le 10^9$, $1 \le W \le 10^9$, and $Q$ is a prime number smaller than $10^8$. The sequence $a_0 \cdots a_{N-1}$ of length $N$ is produced by the following code, where $a_i$ 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; }
}

Here /, %, and ^ are integer division, modulo, and bitwise exclusive-or, respectively. This code is only a pseudo-random generator; the intended solution does not depend on 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 on its own line. You may assume that the answer is smaller than $2^{30}$.

The same number is counted once for each pair of positions $(i, j)$ that produces it. For example, if the sequence is $421$ and $Q = 7$, the multiples of $7$ are $42$ and $21$, so the answer is $2$. If the sequence is $5052$ and $Q = 5$, the multiples of $5$ are $5$, $50$, $505$, and $5$ again, for a total of $4$. The values $0$ and $05$ are not counted, because a considered subsequence must start at a nonzero digit (no leading zeros) and represent a positive integer; the digit $5$ is counted twice because it appears at two different positions. For reference, the first four datasets of the sample input generate the sequences $421$, $5052$, $95073$, and $12221$.