E - Couple /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 100

問題文

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

入力

入力は以下の形式で標準入力から与えられる。

N
P_1 
P_2
:
P_N

出力

条件を満たす座り方の数を 924844033 で割った余りで出力せよ。


入力例 1

2
1
2

出力例 1

1

条件を満たす座り方は 12341 通りである。 例えば 12432 番目のうくさんと 4 番目のひふみさんが隣接しているため条件を満たさない。


入力例 2

3
1
2
6

出力例 2

3

1246531264531265433 通りである。


入力例 3

10
2
3
5
6
8
9
11
12
13
14

出力例 3

1561440