置换的周期

令 $i_1,i_2,i_3,\dots ,i_n$ 为集合 $\{1,2,3,...,n\}$ 的排列，其中 $n$ 为正整数。排列也可以被视为函数 $f$。我们用 2-by-$n$ 数组表示此排列 $$f=\left(\begin{array}{cccc}1& 2& \cdots & n\\ i_1& i_2& \cdots & i_n\end{array}\right)$$ 它将编号 1 映射到 $i_1$，将编号 2 映射到 $i_2$，依此类推。当该函数对集合$1,2,3,...,n$的排列，即$x_1,x_2,x_3,\cdots ,x_n$进行操作时，可以获得新的排列$y_1,y_2,y_3,\cdots ,y_n$。这里是$y_1=f(x_1),y_2=f(x_2),\cdots ,y_n=f(x_n)$。

例如，当 $n=4$ 和 $2,4,1,3$ 存在排列时。我们让这个排列连续地运行在一个排列 $1,2,3,4$ 上，那么它将是 $$1,2,3,4\to 2,4,1,3\to 4,3,2,1\to 3,1,4,2\to 1,2,3,4\to \cdots$$ 显然，在 4 操作之后，结果排列返回到初始排列。

令 $F(l,p)$ 为集合 $\{1,2,3,...,l\}$ 的排列数，这使得排列 $1,2,3,\cdots ,l$ 在 $p$ 操作后返回到其自身。例如，$F(4,3)=9$，因为存在满足条件的 9 排列：$(1,2,3,4)$、$(1,3,4,2)$、$(1,4,2,3)$、$(2,3,1,4)$、$(2,4,3,1)$、$(3,1,2,4)$、$(3,2,4,1)$、$(4,1,3,2)$、$(4,2,1,3)$。您还获得了 $F(5,5)=25$、$F(10,6)=625176$、$F(20,11)=609493248001$。

让$S(L,P)={\sum }_{l=1}^L{\sum }_{p=1}^{P}F(l,p)$。找到 $S(10000,1000)mod1000000007$。

---

感谢 百黑客 为了这个想法。