30025번 - 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)$로 나눈 나머지를 출력한다. 이 수는 소수이다.

제한

힌트