34083번 - 결계 배치하기

문제

영문을 모르겠어!

∧ ∧

↙( ◕ ‿‿ ◕ )↘

1ドル$ 이상 $K$ 이하의 정수들을 좌표로 가지는 수직선 위에 $N$개의 에너지원이 각각 1ドル\leq a_1<a_2<\cdots <a_N\leq K$ 위치에 있다. 큐베는 이 수직선 위에 결계들을 적절히 배치하여, 에너지원들이 결계와 충돌하게끔 해 이때 발산되는 에너지를 모으는 일을 한다. 큐베는 $M$ ($M$은 $N$의 약수)개의 서로 다른 오름차순 정수 1ドル\leq b_1<b_2<\cdots <b_M\leq K$을 선택하여 그 위치들에 동시에 결계를 설치하려고 한다. 에너지원이 있는 위치에도 결계를 배치할 수 있다.

결계에는 에너지원들을 유인하는 효과가 있어서, 각 에너지원들은 좌표의 차가 가장 작은 결계로 이동하여 충돌한다. 만약 그러한 결계가 둘이라면 좌표가 더 작은 결계로 이동하여 충돌한다.

큐베는 안정성을 위해 각 결계가 정확히 $\cfrac{N}{M}$개씩의 에너지원과만 충돌하게끔 결계를 배치하려고 한다. 가능한 모든 미래에서 큐베가 서로 다른 순서쌍 $(b_1,b_2,\cdots ,b_M)$을 선택하는 경우의 수를 계산해 주자.

입력

첫 번째 줄에 세 정수 $N,ドル $M,ドル $K$가 공백으로 구분되어 주어진다. (2ドル\leq M\leq N\leq 2 ,円 000 ; M$은 $N$의 약수$ ; N\leq K\leq 10 ,円 000$)

두 번째 줄에 $N$개의 정수 $a_1,a_2,\cdots ,a_N$이 공백으로 구분되어 주어진다. $(1\leq a_1<a_2<\cdots <a_N\leq K)$

출력

큐베가 서로 다른 순서쌍 $(b_1,b_2,\cdots ,b_M)$을 선택하는 경우의 수를 998ドル,円 244,円 353$으로 나눈 나머지를 출력한다.

제한

노트

어떤 두 순서쌍 $(x_1, x_2, \cdots, x_M)$과 $(y_1, y_2, \cdots, y_M$)이 서로 다르다는 것은 $x_i \neq y_i$인 $i$가 존재함과 동치이다.