問題文

1 から N まで番号づけされた N 人のうくさんと、N+1 から 2N まで番号づけされた N 人のひふみさんがいる。

すべての 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
• 入力は全て整数

入力例 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