配点 : 100点

問題文

$N$ 個の整数 $A_1, A_2, ..., A_N$ があります。

$(1, 2, ..., N)$ の順列 $P = (P_1, P_2, ..., P_N)$ であって次の条件を満たすものの個数を求めてください：

• $1 \leq i \leq N-1$ なる任意の整数 $i$ について、次が成り立つ：
  • $\displaystyle \Large A_{P_i} \leq A_{P_{i + 1}}$

ただし、答えは非常に大きくなる場合があるので、$998244353$ で割ったあまりを出力してください。

制約

• $1 \leq N \leq 3 \times 10^5$
• $0 \leq A_i < 2^{30} \scriptsize \; (1 \leq i \leq N)$
• 入力はすべて整数である。

入力

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

出力

答えを求め、$998244353$ で割ったあまりを標準出力へ出力せよ。

入出力例1

3
3 1 5

1

$P = (2, 1, 3)$ のみが条件を満たします。

入出力例2

5
3 1 4 1 5

2

$P \in \{\, (2, 4, 1, 3, 5), (4, 2, 1, 3, 5) \,\}$ のとき、またこのときに限り、条件が満たされます。

入出力例3

9
1 4 1 4 2 1 3 5 6

12