You are given a sequence \textbf{a_0a_1...a_\{N−1\}} of digits and a prime number \textbf{Q}. For each \textbf{i} ≤ \textbf{j} with \textbf{a_i ≠ 0}, the subsequence\textbf{a_ia_\{i+1\}...a_j} can be read \textbf{a_s} a decimal representation of a positive integer. Subsequences with leading zeros are not considered. Your task is to count the number of pairs (\textbf{i}, \textbf{j}) such that the corresponding subsequence is a multiple of \textbf{Q}. \InputFile The input consists of at most \textbf{50} datasets. Each dataset is represented by a line containing four integers \textbf{N}, \textbf{S}, \textbf{W}, and \textbf{Q}, separated by spaces, where \textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}, \textbf{1} ≤ \textbf{S} ≤ \textbf{10^9}, \textbf{1} ≤ \textbf{W} ≤ \textbf{10^9}, and \textbf{Q} is a prime number less than \textbf{10^8}. The sequence \textbf{a_0...a_\{N−1\}} of length \textbf{N} is generated by the following code, in which ai is written as \textbf{a\[i\]}. \textbf{int g = S; for(int i=0; i a\[i\] = (g/7) \% 10; if( g\%2 == 0 ) \{ g = (g/2); \} else \{ g = (g/2) ^ W; \} \}} Note: the operators \textbf{/}, \textbf{\%}, and \textbf{^} 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. \OutputFile For each dataset, output the answer in a line. You may assume that the answer is less than \textbf{2^30}. \textit{\textbf{Note for sample}}: In the first dataset, the sequence is \textbf{421}. We can find two multiples of \textbf{Q = 7}, namely, \textbf{42} and \textbf{21}. In the second dataset, the sequence is \textbf{5052}, from which we can find \textbf{5}, \textbf{50}, \textbf{505}, and \textbf{5} being the multiples of \textbf{Q = 5}. Notice that we don’t count \textbf{0} or \textbf{05} since they are not a valid representation of positive integers. Also notice that we count \textbf{5} twice, because it occurs twice in different positions. In the third and fourth datasets, the sequences are \textbf{95073} and \textbf{12221}, respectively.