Problem Statement

You are given a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$.

Print the number of integer sequences $A = (A_1, A_2, \ldots, A_N)$ of length $N$ that satisfy both of the conditions below, modulo $998244353$.

• $1 \leq A_i \leq M$ for every $i = 1, 2, \ldots, N$.
• The integer sequence $A$ is lexicographically smaller than the integer sequence $(A_{P_1}, A_{P_2}, \ldots, A_{P_N})$.

What is lexicographical order? An integer sequence $X = (X_1,X_2,\ldots,X_N)$ is ** lexicographically smaller** than an integer sequence $Y = (Y_1,Y_2,\ldots,Y_N)$ when there is an integer $1 \leq i \leq N$ that satisfies both of the conditions below. For all integers $j$ ($1 \leq j \leq i-1$), $X_j=Y_j$. $X_i < Y_i$

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 10^9$
• $1 \leq P_i \leq N$
• $i \neq j \implies P_i \neq P_j$
• All values in the input are integers.

Input

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

N M
P_1 P_2 \ldots P_N

Output

Print the number of integer sequences $A$ of length $N$ that satisfy both of the conditions in the Problem Statement, modulo $998244353$.