← 返回题目列表

AtCoder · ukuku09_e

E. 情侣

中文机器翻译题面 查看原题

配点 : 100 点

問題文

1 减去 N 的分割, N 个人的Uku桑和N+1 减去 2N 的分割, N 个人的Hifumi桑。

全部 i(1 \leq i \leq N) ,i 号的乌久先生和 i+N 号的日文女士彼此已知是情侣。

今、2N 张椅子横 1 排排列着,已经 N 人坐着。j 第几个人从左边算 P_j 个椅子上坐着。

从现在开始,N 人坐在空着的椅子上。但如果情侣坐在相邻的椅子上,他们会互相亲昵,因此应避免出现这种情况的安排。

满足条件的坐法数量为 924844033 除以后的余数求出。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq P_j \leq 2N
  • j \neq k 如果 P_j \neq P_k
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
P_1 
P_2
:
P_N

出力

满足条件的坐法数量为 924844033 输出除以后的余数。


入力例 1

2
1
2

出力例 1

1

满足条件的坐法是 1234 可以得到第 1 是正确的。 例如 1243 是 您也可以写 2 第几位的乌库先生和 4 第几位的希富米先生相邻,因此不满足条件。


入力例 2

3
1
2
6

出力例 2

3

124653、126453、126543 可以得到第 3 没错。


入力例 3

10
2
3
5
6
8
9
11
12
13
14

出力例 3

1561440