問題一覧 > 通常問題

No.1428 PeRmutation Question

レベル : / AI推定難易度 : 2250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : 👑 箱星 / テスター : butsurizuki
お気に入りにしたユーザー ProblemId : 5098 / 自分の提出
問題文最終更新日: 2022-04-26 00:01:45
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 286 (順位表) の他の問題:

Problem Statement

You are given a permutation $P$ of $1,2,\ldots, N$.

Find the number of permutations $Q$ of $1,2,\ldots,N$ that satisfy the following condition.

  • (Condition on $Q$) There exists a permutation $R$ of $1,2,\ldots,N$ that satisfies the following $2$ conditions.
    • (Condition $1$ on $R$) $P_{R_i}=R_{Q_i} \ (i=1,2,\ldots,N)$
    • (Condition $2$ on $R$) The inversion number of $R$ is even.

Since the answer can be very large, find the answer modulo $10^9+7$.

Input

$N$
$P_1$ $P_2$ $\ldots$ $P_N$
  • All inputs are integers.
  • $1\le N\le 10^5$
  • $P_1,P_2,\ldots,P_N$ is a permutation of $1,2,\ldots,N$.

Output

Find the number of permutations satisfying the condition, and output it modulo $10^9+7$.

Sample

Sample 1
Input
4
2 1 4 3
Output
3

For example, $Q=(4,3,2,1)$ satisfies the condition by taking $R=(3,1,2,4)$.

Sample 2
Input
1
1
Output
1

Sample 3
Input
9
3 5 1 8 9 7 4 6 2
Output
15120

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