시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB23017115675.362%

문제

준혁이는 $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

예제 입력 4

2 30 2
2 4

예제 출력 4

73741817

출처

University > 충남대학교 > 2023 충남대학교 SW-IT Contest > Division 1 I번