결계 배치하기

영문을 모르겠어!

　∧　　 ∧

↙( ◕ ‿‿ ◕ )↘

$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$가 존재함과 동치이다.