問題文

正整数 N と長さ N の非負整数列 A が与えられる。以下の操作をちょうど K 回繰り返すことを考える。

• A から正の要素をひとつ選ぶ。選んだ要素を x として、これを 0 \leq y < x を満たす整数 y に置き換える。

K 回の操作の後の A としてあり得るものの数を 998244353 で割った余りを求めよ。

制約

• 1 \leq N \leq 10^5
• 1 \leq K \leq 10^5
• 0 \leq A_i \leq 10^9
• 入力は全て整数

配点

以下の小課題に点数が定められている。

1. (200 点) N, K \leq 100
2. (400 点) N, K \leq 1000
3. (200 点) 追加の制約はない。

入力例 1

3 2
1 2 3

出力例 1

14

K 回の操作後の A としてあり得るものを以下に列挙する : (1, 2, 1), (1, 2, 0), (1, 1, 2), (1, 1, 1), (1, 1, 0), (1, 0, 3), (1, 0, 2), (1, 0, 1), (1, 0, 0), (0, 2, 2), (0, 2, 1), (0, 2, 0), (0, 1, 3), (0, 0, 3) の 14 通り。

入力例 2

5 3
1 2 3 4 5

出力例 2

306