시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB52121157.895%

문제

민호는 b개의 바구니를 가지고 있다. 모든 바구니에는 1부터 9까지중 한개의 자연수가 적힌 블록 n개가 들어가 있다. 바구니에 들어가있는 블록의 종류는 서로 다 동일하다. 즉 첫 번째 바구니에 [1, 1, 2, 3]의 블록이 들어가 있으면 모든 바구니 안에는 각각 [1, 1, 2, 3]의 블록들이 들어가 있다는 얘기다.

민호는 첫 번째 바구니에서부터 마지막 바구니까지 정확히 한개의 블록을 꺼내 차례대로 이어 붙여 매우 큰 숫자를 만들 계획이다. 예를 들어 바구니가 두개 있고 첫 번째 바구니에서 1이 적힌 블록을 꺼내고 두 번째 바구니에서 2가 적힌 블록을 꺼냈다면 12가 만들어 진다. 블록의 순서를 바꿀수는 없다. 즉 21이 될 수 없다는 얘기다.

한 바구니에 똑같은 숫자가 적힌 블록들이 여러개가 있을 수 있는데 이는 서로 다른 경우의 수라 생각을 한다.

하지만 숫자가 너무 커져 기억을 하기 힘든 민호는 이 수를 x로 나눈 나머지가 k가 될때만 기억하기로 했다. 이때 민호가 기억을 해야하는 경우의 수는 몇 가지인지 알아보자.

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

입력

첫 번째 줄에 n, b, k, x가 공백을 구분으로 주어진다. (2 ≤ n ≤ 500,000, 1 ≤ b ≤ 109, 0 ≤ k ≤ x - 1 ≤ 100, 2 ≤ x)

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

출력

각각의 바구니에서 정확히 한개의 블록을 선택해 만든 수를 x로 나눈 나머지가 k가 되는 경우의 수를 109 + 7로 나눈 나머지를 출력한다.

예제 입력 1

12 1 5 10
3 5 6 7 8 9 5 1 1 1 1 5

예제 출력 1

3

예제 입력 2

3 2 1 2
6 2 2

예제 출력 2

0

예제 입력 3

3 2 1 2
3 1 2

예제 출력 3

6

출처