問題文

$1,2,\ldots, N$ の順列 $P$ が与えられます。

次の条件を満たす $1,2,\ldots,N$ の順列 $Q$ がいくつあるかを求めてください。

• ($Q$ に関する条件) 以下の $2$ つの条件を満たす $1,2,\ldots,N$ の順列 $R$ が存在する。
  • ($R$ に関する条件 $1$) $P_{R_i}=R_{Q_i} \ (i=1,2,\ldots,N)$
  • ($R$ に関する条件 $2$) $R$ の転倒数は偶数

ただし答えは非常に大きくなる場合があるので、答えを $10^9+7$ で割った余りを求めてください。

入力

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

• 入力はすべて整数
• $1\le N\le 10^5$
• $P_1,P_2,\ldots,P_N$ は $1,2,\ldots,N$ の順列

出力

条件を満たす順列がいくつあるかを求め、$10^9+7$ で割った余りを出力してください。

サンプル

4
2 1 4 3

3

1
1

1

9
3 5 1 8 9 7 4 6 2

15120