给定一个 $\{1, 2, \dots, n\}$ 的排列 $P$，求满足对于所有 $i \in \{1, 2, \dots, n - 1\}$，都有 $Q_{i+1} \neq P_{Q_i}$ 的 $\{1, 2, \dots, n\}$ 的排列 $Q$ 的数量。输出该数量对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示给定排列的大小。 第二行包含 $n$ 个整数 $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$)，表示给定的排列。 保证 $\{P_1, P_2, \dots, P_n\} = \{1, 2, \dots, n\}$。

输出格式

输出一行，包含一个整数，表示答案对 $998244353$ 取模的结果。

样例

输入格式 1

4
3 4 1 2

输出格式 1

8

说明

这 8 个排列分别是：

• $\{1, 2, 3, 4\}$
• $\{1, 4, 3, 2\}$
• $\{2, 1, 4, 3\}$
• $\{2, 3, 4, 1\}$
• $\{3, 2, 1, 4\}$
• $\{3, 4, 1, 2\}$
• $\{4, 1, 2, 3\}$
• $\{4, 3, 2, 1\}$