给你一个由数字组成的序列 $a_0 a_1 \cdots a_{N-1}$ 和一个质数 $Q$。对于满足 $a_i \ne 0$ 的每个 $i \le j$，子序列 $a_i a_{i+1} \cdots a_j$ 可以被视作一个正整数的十进制表示。不考虑含有前导零的子序列。你的任务是统计满足其对应子序列是 $Q$ 的倍数的数对 $(i, j)$ 的数量。

输入格式

输入最多包含 50 组数据。每组数据由一行包含四个空格隔开的整数 $N, S, W$ 和 $Q$ 表示，其中 $1 \le N \le 10^5$，$1 \le S \le 10^9$，$1 \le W \le 10^9$，且 $Q$ 是一个小于 $10^8$ 的质数。长度为 $N$ 的序列 $a_0 \cdots a_{N-1}$ 由以下代码生成，其中 $a_i$ 写作 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; }
}

注意：运算符 /、% 和 ^ 分别表示整除、取模和按位异或。上述代码旨在作为一个随机数生成器。本题的预期解法不依赖于序列的具体生成方式。

输入结束由一行包含四个由空格隔开的零（0 0 0 0）表示。

输出格式

对于每组数据，在一行中输出答案。你可以假设答案小于 $2^{30}$。

样例

输入样例 1

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

输出样例 1

2
4
6
3
68530

说明

在第一个数据集中，生成的序列为 421。我们可以找到两个 $Q = 7$ 的倍数，即 42 和 21。

在第二个数据集中，生成的序列为 5052，其中我们可以找到 5、50、505 和 5 作为 $Q = 5$ 的倍数。请注意，我们不统计 0 或 05，因为它们不是正整数的有效表示。同时请注意，我们统计了两次 5，因为它在不同的位置出现了两次。

在第三个和第四个数据集中，生成的序列分别为 95073 和 12221。