No.573 a^2[i] = a[i]
startcpp
ixmel
問題文最終更新日: 2026-06-28 17:14:59
English (AI translation)
a^2[i] = a[i]
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. Show the original
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. Show the original
yukicoder contest 174
(順位表)
の他の問題:
Problem Statement
For all $i$ ($0 \le i \le N - 1$),
・$0 \le a[i] \le N - 1$
・$a[a[i]]$ = $a[i]$
How many integer sequences {$a[0], a[1], …, a[N - 1]$} satisfy both of these conditions?
Find the answer modulo $10^9 + 7$.
Input
N
$1 \le N \le 100000$
Output
If there are $X$ sequences satisfying the conditions, print the remainder of $X$ divided by $10^9 + 7$.
Print a newline at the end.
Sample
Sample 1
Input
3
Output
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$}
These $10$ sequences satisfy the conditions.
Sample 2
Input
9
Output
293608
Sample 3
Input
100000
Output
818317402
Print the remainder when divided by 10^9 + 7.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。