UOJ Logo

NOI.AC

1S 256MB

#11. A

统计

小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

测试点编号 $n$的规模 约定
1,2$\leq 10$
3,4$\leq 1000$
5$\leq 10^6$保证$p_i = i + 1, p_n = 1$
6,7$\leq 10^6$保证置换每个轮换的大小互不不同
8,9,10$\leq 10^6$