---

Problem 977

---

Iterated Functions

For a positive integer $n$, let $F(n)$ denote the number of functions $f$ from the set $S_n=\{1,2,\dots,n\}$ to itself such that $f^{(x)}(y)=f^{(y)}(x)$ for any $x,y$ in $S_n$. Here $f^{(k)}$ denotes the $k$-th iterated composition of $f$, e.g. $f^{(2)}(x)=f(f(x))$.

For example, $F(3)=8$, $F(7)=174$, $F(100)=570271270297640131$.

Find $F(10^6) \bmod (10^9+7)$.

---

函数迭代

对于正整数$n$，记$F(n)$为从集合$S_n=\{1,2,\dots,n\}$映射到自身且满足以下条件的函数$f$的个数：对于$S_n$中的任意$x,y$，均有$f^{(x)}(y)=f^{(y)}(x)$，其中$f^{(k)}$表示$f$的$k$次迭代复合，例如$f^{(2)}(x)=f(f(x))$。

已知$F(3)=8$，$F(7)=174$，$F(100)=570271270297640131$。

求$F(10^6) \bmod (10^9+7)$。

---