Remainder Game

Time limit2sMemory limit512 MB

Summary

Count ways to pick one block per basket, forming a b-digit number whose remainder mod x is k, where baskets share the same multiset of digits.

Level: Hard8 of 10
Topics: Dynamic programming, Matrix, Math, Combinatorics
Solved: No attempts yet

Problem

Minho has $b$ baskets. Each basket holds $n$ blocks, and every block is marked with one digit from 1 to 9. Every basket holds the same collection of blocks. If the first basket holds the blocks [1, 1, 2, 3], then every other basket holds [1, 1, 2, 3] as well.

Minho takes exactly one block out of each basket, going from the first basket to the last, and joins the digits in that order to build a $b$ -digit number. With two baskets, taking the block marked 1 from the first basket and the block marked 2 from the second gives 12. The order of the blocks cannot be changed, so 21 cannot be built.

A basket can hold several blocks marked with the same digit, and those blocks count as different blocks. Two choices that take different blocks count separately even when they build the same number.

The numbers get too large to memorize, so Minho decides to remember a number only when its remainder divided by $x$ equals $k$ . Count how many choices Minho ends up remembering.

The count can get very large, so print it modulo $10^9 + 7$ .

Input

The first line contains $n$ , $b$ , $k$ , $x$ , separated by spaces. ( $2 \le n \le 500{,}000$ , $1 \le b \le 10^9$ , $0 \le k \le x - 1 \le 100$ , $2 \le x$ )

The second line contains the $n$ digits written on the blocks of one basket, separated by spaces. Each digit is one of the natural numbers 1 to 9.

Output

Print the number of ways to take exactly one block out of each basket so that the resulting number has remainder $k$ when divided by $x$ , modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5
```
Expected output
```
3
```
Example 2
Input
```
3 2 1 2
6 2 2
```
Expected output
```
0
```
Example 3
Input
```
3 2 1 2
3 1 2
```
Expected output
```
6
```