CF621E.Wet Shark and Blocks

There are b blocks of digits. Each one consisting of the same n digits, which are given to you in the input. Wet Shark must choose exactly one digit from each block and concatenate all of those digits together to form one large integer. For example, if he chooses digit 1 from the first block and digit 2 from the second block, he gets the integer 12.

Wet Shark then takes this number modulo x. Please, tell him how many ways he can choose one digit from each block so that he gets exactly k as the final result. As this number may be too large, print it modulo 109 + 7.

Note, that the number of ways to choose some digit in the block is equal to the number of it's occurrences. For example, there are 3 ways to choose digit 5 from block 3 5 6 7 8 9 5 1 1 1 1 5.

共有 $b$ 个数字块。每个块均由相同的 $n$ 个数字组成，这些数字在输入中给出。Wet Shark 必须从每个块中恰好选择一个数字，并将所有选中的数字按顺序拼接起来，形成一个大的整数。例如，若他从第一个块中选择了数字 1，从第二个块中选择了数字 2，则得到整数 $12$。

接着，Wet Shark 将该整数对 $x$ 取模。请告诉他：有多少种方式，使得从每个块中各选一个数字后拼接成的整数对 $x$ 取模的结果恰好等于 $k$？由于该数目可能非常大，请将结果对 $10^9 + 7$ 取模后输出。

注意：在一个块中选择某个特定数字的方式数，等于该数字在该块中出现的次数。例如，在数字块 3 5 6 7 8 9 5 1 1 1 1 5 中，选择数字 5 的方法数为 $3$。

The first line of the input contains four space-separated integers, n, b, k and x (2 ≤ n ≤ 50 000, 1 ≤ b ≤ 109, 0 ≤ k < x ≤ 100, x ≥ 2) — the number of digits in one block, the number of blocks, interesting remainder modulo x and modulo x itself.

The next line contains n space separated integers a__i (1 ≤ a__i ≤ 9), that give the digits contained in each block.

输入的第一行包含四个以空格分隔的整数 $n$、$b$、$k$ 和 $x$（满足 $2 \leq n \leq 50\,000$，$1 \leq b \leq 10^9$，$0 \leq k < x \leq 100$，$x \geq 2$）—— 分别表示每个块中的数字位数、块的数量、感兴趣的模 $x$ 余数以及模数 $x$ 本身。

下一行包含 $n$ 个以空格分隔的整数 $a_i$（$1 \leq a_i \leq 9$），表示每个块中所含的数字。

Print the number of ways to pick exactly one digit from each blocks, such that the resulting integer equals k modulo x.

从每个块中恰好选取一个数字，使得所组成的整数对 $x$ 取模的结果等于 $k$，输出满足条件的选取方式总数。

In the second sample possible integers are 22, 26, 62 and 66. None of them gives the remainder 1 modulo 2.

In the third sample integers 11, 13, 21, 23, 31 and 33 have remainder 1 modulo 2. There is exactly one way to obtain each of these integers, so the total answer is 6.

在第二个样例中，可能的整数为 $22$、$26$、$62$ 和 $66$。这些数中没有一个对 $2$ 取模余 $1$。

在第三个样例中，整数 $11$、$13$、$21$、$23$、$31$ 和 $33$ 对 $2$ 取模余 $1$。每个这样的整数恰好有一种方式得到，因此总答案为 $6$。