問題一覧 > 通常問題

No.573 a^2[i] = a[i]

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 135
作問者 : startcpp / テスター : ixmel
4 ProblemId : 1487 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-10-06 23:04:28

問題文

全てのi(0≤i≤N−1)について、
・0≤a[i]≤N−1
・a[a[i]] = a[i]
を共に満たす整数列{a[0],a[1],…,a[N−1]}は何通りありますか？

109+7で割った余りを求めてください。

入力

N

1≤N≤100000

出力

条件を満たす数列がX通りあるとき、Xを109+7で割った余りを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
出力
10

a = {0,0,0}, {0,0,2}, {0,1,0}, {0,1,1}, {0,1,2}, {0,2,2}, {1,1,1}, {1,1,2}, {2,1,2}, {2,2,2}
の10通りが条件を満たします。

サンプル2
入力
9
出力
293608

サンプル3
入力
100000
出力
818317402

10^9 + 7で割った余りを出力してください。

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