小w要造一个送分的置换。所谓置换，就是两排$1$到$n$的数字用括号括起来。比如 $\begin{pmatrix}1&2&3&4&5 \\ 2&5&4&3&1\end{pmatrix}$ 就是一个置换，它表示的是把本来在$1$位置的数字变换到位置$2$，把在$2$位置的数字变换到位置$5$，etc.

然而小w的妹妹jz患有阅读障碍，在她的眼里，数字$i$会被看成数字$a_i$，其中$a$是一个排列，也就是说$\forall_{i \not= j} \ a_i \not= a_j$。小w非常疼爱自己的妹妹jz，可是他却因为不知道排列$a$，难以理解自己的妹妹。

为了能更好的理解自己的妹妹，他想要知道，对于一个置换$\begin{pmatrix}1&\cdots&i&\cdots&n \\ p_1&\cdots&p_i&\cdots&p_n\end{pmatrix}$，她的妹妹眼里的置换有多少种本质不同的可能呢？答案对$998244353$取模后输出。

两个置换本质相同当且仅当每次交换两列把第一排数排好序之后，第二行数相同。

输入格式

第一行一个整数$n$。

第二行一共$n$个整数，$p_1, p_2, \cdots, p_n$。

输出格式

一行一个整数表示对$998244353$取模之后的答案。

样例一

input

5
2 1 4 5 3

output

20

数据范围

时间限制1s, 空间限制256MB