K의 배수

문제

준혁이는 $0$부터 $9$까지의 숫자 중에서 서로 다른 숫자를 $N$개 골랐다. 준혁이가 고른 숫자만으로 이루어진 $M$자리의 양의 정수 중에서 $K$의 배수는 몇 개인지 구해보자. 단, $M$자리의 양의 정수는 숫자 $0$으로 시작할 수 없으며, 조건을 만족하는 양의 정수가 매우 많을 수 있기 때문에 그 개수를 $1\,000\,000\,007(= 10^9+7)$로 나눈 나머지를 구한다. 이 수는 소수이다.

입력

첫째 줄에 정수 $N, M, K(1 \le N \le 10; 1 \le M \le 100; 2 \le K \le 1\,000)$이 공백으로 구분되어 주어진다.

둘째 줄에 준혁이가 고른 숫자 $a_1, a_2, \cdots, a_N(0 \le a_i \le 9)$이 공백으로 구분되어 오름차순으로 주어진다.

출력

준혁이가 고른 숫자만으로 이루어진 $M$자리의 양의 정수 중에서 $K$의 배수의 개수를 $1\,000\,000\,007(= 10^9+7)$로 나눈 나머지를 출력한다. 이 수는 소수이다.

예제 입력 1

10 1 2
0 1 2 3 4 5 6 7 8 9

예제 출력 1

4

예제 입력 2

5 2 25
0 1 2 5 7

예제 출력 2

3

예제 입력 3

2 2 2
0 2

예제 출력 3

2

예제 입력 3

2 30 2
2 4

예제 출력 3

73741817