나머지 게임

민호는 바구니 $b$개를 가지고 있다. 바구니마다 1부터 9까지의 자연수 중 하나가 적힌 블록이 $n$개씩 들어 있고, 어느 바구니를 열어도 블록의 구성은 똑같다. 첫 번째 바구니에 블록 [1, 1, 2, 3]이 들어 있으면 나머지 바구니에도 [1, 1, 2, 3]이 들어 있다.

민호는 첫 번째 바구니부터 마지막 바구니까지 각 바구니에서 블록을 정확히 하나씩 꺼내, 꺼낸 순서대로 숫자를 이어 붙여 $b$자리 수를 만든다. 바구니가 두 개이고 첫 번째 바구니에서 1이 적힌 블록, 두 번째 바구니에서 2가 적힌 블록을 꺼냈다면 12가 된다. 블록의 순서는 바꿀 수 없다. 즉 21은 만들 수 없다.

한 바구니에 같은 숫자가 적힌 블록이 여러 개 들어 있을 수 있고, 이 블록은 서로 다른 블록으로 센다. 꺼낸 블록이 다르면 만들어진 수가 같아도 다른 경우로 센다.

수가 너무 커서 외우기 힘든 민호는 만든 수를 $x$로 나눈 나머지가 $k$일 때만 그 수를 기억하기로 했다. 민호가 기억하게 되는 경우가 몇 가지인지 구하자.

경우의 수가 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫째 줄에 $n$, $b$, $k$, $x$가 공백으로 구분되어 주어진다. ($2 \le n \le 500{,}000$, $1 \le b \le 10^9$, $0 \le k \le x - 1 \le 100$, $2 \le x$)

둘째 줄에 바구니 하나에 들어 있는 블록에 적힌 숫자 $n$개가 공백으로 구분되어 주어진다. 각 숫자는 1부터 9까지의 자연수 중 하나이다.

각 바구니에서 블록을 정확히 하나씩 꺼내 만든 수를 $x$로 나눈 나머지가 $k$가 되는 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.