配点 : 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