問題文

正整数 N,M と長さ N の整数列 T=(T_1,T_2,\ldots,T_N),A=(A_1,A_2,\ldots,A_N) が与えられます。

すべての要素が 1 以上 M 以下である長さ N+1 の正整数列 b=(b_1,b_2,\ldots,b_{N+1}) であって、すべての i\ (1 \le i \le N) について以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

• T_i=0 のとき、 \min(b_i,b_{i+1})=A_i
• T_i=1 のとき、 \max(b_i,b_{i+1})=A_i

制約

• 1 \le N, M \le 2 \times 10^5
• T_i \in \{0, 1 \}
• 1 \le A_i \le M
• 入力は全て整数

入力例 1

2 2
0 0
1 2

出力例 1

1

b=(1,2,2) の時条件を満たします。

入力例 2

2 4
0 1
1 2

出力例 2

6

入力例 3

15 509
1 0 1 1 1 1 0 1 1 1 1 1 1 0 0
367 241 241 160 160 156 156 459 395 288 288 408 505 270 270

出力例 3

684062245

998244353 で割った余りを求めることをお忘れなく。

原案: turtle0123__