問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 108
作問者 : startcppstartcpp / テスター : ixmelixmel
3 ProblemId : 1487 / 出題時の順位表
問題文最終更新日: 2017-10-06 23:04:28

問題文

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

$10^9 + 7$で割った余りを求めてください。

入力

N

$1 \le N \le 100000$

出力

条件を満たす数列が$X$通りあるとき、$X$を$10^9 + 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もしくは右上の雲マークをクリックしてアカウントを作成してください。