問題一覧 > 通常問題

No.1428 PeRmutation Question

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 16
作問者 : 👑 koboshikoboshi / テスター : butsurizukibutsurizuki
2 ProblemId : 5098 / 出題時の順位表
問題文最終更新日: 2021-01-04 13:36:00

問題文

$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$ で割った余りを出力してください。

サンプル

サンプル1
入力
4
2 1 4 3
出力
3

例えば、$Q=(4,3,2,1)$ は、$R=(3,1,2,4)$ とすれば条件を満たします。

サンプル2
入力
1
1
出力
1

サンプル3
入力
9
3 5 1 8 9 7 4 6 2
出力
15120

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。