시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB21161376.471%

문제

양의 정수 $N$과 길이 $M$의 정수 수열 $A=(A_1, A_2, \cdots, A_M)$이 주어진다. 이때, 다음을 만족하는 함수 $f$의 개수를 구하라.

  • $f : \left\{1, \, 2, \, \cdots, \, N \right\} \rightarrow \left\{1, \, 2, \, \cdots, \, N \right\}$.
  • $\left\{\, f^{(K)}(x) \mid x \in \left\{1,2,\cdots,N\right\} \,\right\}\,$$\cup \left\{ A_1, \, A_2, \, \cdots, A_M \right\}\,$$= \left\{1, 2,\cdots, N\right\}$. 이때, $f^{(K)}(x) := \underbrace{f(f(\cdots f}_{K\text{번}}(x)\cdots))$이다.

이때, 답이 매우 커질 수 있으므로 $998 \, 244 \, 353$으로 나눈 나머지를 출력하라. $998 \, 244 \, 353$은 소수이다.

입력

첫 번째 줄에 정수 $N, \, M, \, K$가 공백으로 구분되어 주어진다. ($1 \leq M \leq N \leq 50$; $1\leq K \leq 10^8$)

두 번째 줄에 수열 $A$의 원소 $A_1, \, A_2, \, \cdots, \, A_M$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq N$; $A_i$는 모두 다르다.)

출력

첫 번째 줄에 조건을 만족하는 함수 $f$의 개수를 $998 \, 244 \, 353$으로 나눈 나머지를 출력하라.

예제 입력 1

3 2 1
3 1

예제 출력 1

19

예제 입력 2

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

예제 출력 2

17556470

예제 입력 3

5 2 2
4 5

예제 출력 3

438