Problem Description

Given positive integers \( N, M \) and integer sequences \( T = (T_1, T_2, \ldots, T_N), A = (A_1, A_2, \ldots, A_N) \) of length \( N \), find the number of sequences \( b = (b_1, b_2, \ldots, b_{N+1}) \) of length \( N+1 \) where all elements are between 1 and \( M \) (inclusive), such that for all \( i \) ( \( 1 \le i \le N \) ), the following conditions are satisfied:

• If \( T_i = 0 \), then \( \min(b_i, b_{i+1}) = A_i \)
• If \( T_i = 1 \), then \( \max(b_i, b_{i+1}) = A_i \)

The answer should be the remainder when divided by \( 998244353 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( M \) \( T_1 \) \( T_2 \) \( \ldots \) \( T_N \) \( A_1 \) \( A_2 \) \( \ldots \) \( A_N \)

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

2 2
0 0
1 2

Sample Output #1

1

Sample Input #2

2 4
0 1
1 2

Sample Output #2

6

Sample Input #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

Sample Output #3

684062245

Notes/Hints

Constraints

• \( 1 \le N, M \le 2 \times 10^5 \)
• \( T_i \in \{0, 1\} \)
• \( 1 \le A_i \le M \)
• All inputs are integers

Sample Explanation 1

When \( b = (1, 2, 2) \), the conditions are satisfied.

Sample Explanation 3

Remember to find the remainder when divided by \( 998244353 \). Original idea: [MATH0]

见题面 Input 部分

见题面 Output 部分