E - Missing Subsequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1000 点

問題文

1,\dots,K からなる長さ M の整数列 (X_1,\dots,X_M) が与えられます。

1,\dots,K からなる長さ N の整数列 (A_1,\dots,A_N) のうち、以下の条件を満たすものの数を 998244353 で割ったあまりを求めてください。

  • 1,\dots,K からなる長さ M の整数列のうち、(A_1,\dots,A_N) の（連続とは限らない）部分列として取れないものは (X_1,\dots,X_M) のみ

制約

  • 2\le M,K \le N \le 400
  • 1\le X_i \le K
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M K
X_1 X_2 \dots X_M

出力

条件を満たす数列の数を 998244353 で割ったあまりを出力せよ。

入力例 1

5 2 3
1 1

出力例 1

4

以下の 4 通りが条件を満たします。

  • (2, 3, 1, 2, 3)
  • (2, 3, 1, 3, 2)
  • (3, 2, 1, 2, 3)
  • (3, 2, 1, 3, 2)

入力例 2

400 3 9
1 8 6

出力例 2

417833302

入力例 3

29 3 10
3 3 3

出力例 3

495293602

入力例 4

29 3 10
3 3 4

出力例 4

0

Score : 1000 points

Problem Statement

You are given a sequence of integers (X_1,\dots,X_M) of length M consisting of 1,\dots,K.

Find the number of sequences (A_1,\dots,A_N) of length N consisting of 1,\dots,K that satisfy the following condition, modulo 998244353:

  • Among all sequences of length M consisting of 1,\dots,K, the only sequence that cannot be obtained as a (not necessarily contiguous) subsequence of (A_1,\dots,A_N) is (X_1,\dots,X_M).

Constraints

  • 2\le M,K \le N \le 400
  • 1\le X_i \le K
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M K
X_1 X_2 \dots X_M

Output

Print the number of sequences satisfying the condition, modulo 998244353.

Sample Input 1

5 2 3
1 1

Sample Output 1

4

The following four sequences satisfy the condition:

  • (2, 3, 1, 2, 3)
  • (2, 3, 1, 3, 2)
  • (3, 2, 1, 2, 3)
  • (3, 2, 1, 3, 2)

Sample Input 2

400 3 9
1 8 6

Sample Output 2

417833302

Sample Input 3

29 3 10
3 3 3

Sample Output 3

495293602

Sample Input 4

29 3 10
3 3 4

Sample Output 4

0