No.573 a^2[i] = a[i]
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 134
作問者 :
startcpp
/ テスター :
ixmel
タグ : / 解いたユーザー数 134
作問者 :
startcpp
/ テスター :
ixmel
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。