---

Problem 902

---

Permutation Powers

A permutation $\pi$ of $\{1,\dots ,n\}$ can be represented in one-line notation as $\pi (1),\dots ,\pi (n)$. If all $n!$ permutations are written in lexicographic order then $\text{rank}(\pi )$ is the position of $\pi$ in this $1$-based list.

For example, $\text{rank}(2,1,3)=3$ because the six permutations of $\{1,2,3\}$ in lexicographic order are:
$$1,2,31,3,22,1,32,3,13,1,23,2,1$$

For a positive integer $m$, we define the following permutation of $\{1,\dots ,n\}$ with $n=\frac{m(m+1)}{2}$:
$$\begin{array}{rl}\sigma (i)& =\{\begin{array}{ll}\frac{k(k-1)}{2}+1& \text{if }i=\frac{k(k+1)}{2}\text{ for }k\in \{1,\dots ,m\};\\ i+1& \text{otherwise};\end{array}\\ \tau (i)& =(({10}^9+7)imodn)+1\\ \pi (i)& ={\tau }^{-1}(\sigma (\tau (i)))\end{array}$$
where ${\tau }^{-1}$ is the inverse permutation of $\tau$.

Define ${\displaystyle P(m)=\sum _{k=1}^{m!}\text{rank}({\pi }^k)}$, where ${\pi }^k$ is the permutation arising from applying $\pi$ $k$ times.

For example, $P(2)=4$, $P(3)=780$ and $P(4)=38810300$.

Find $P(100)$. Give your answer modulo $({10}^9+7)$.

---

置换的幂

集合$\{1,\dots ,n\}$的任意置换$\pi$可以用一行记法表示为$\pi (1),\dots ,\pi (n)$。如果将所有$n!$个置换按字典序排列，那么$\text{rank}(\pi )$即是置换$\pi$在这个排列中的位置（从$1$开始计数）。

例如，$\text{rank}(2,1,3)=3$，因为$\{1,2,3\}$的六个置换按字典序排列为：
$$1,2,31,3,22,1,32,3,13,1,23,2,1$$

对于正整数$m$，令$n=\frac{m(m+1)}{2}$，并定义如下$\{1,\dots ,n\}$的置换：
$$\begin{array}{rl}\sigma (i)& =\{\begin{array}{ll}\frac{k(k-1)}{2}+1& \text{若存在}k\in \{1,\dots ,m\}\text{使得}i=\frac{k(k+1)}{2};\\ i+1& \text{其它情形};\end{array}\\ \tau (i)& =(({10}^9+7)imodn)+1\\ \pi (i)& ={\tau }^{-1}(\sigma (\tau (i)))\end{array}$$
其中${\tau }^{-1}$表示$\tau$的逆置换。

定义${\displaystyle P(m)=\sum _{k=1}^{m!}\text{rank}({\pi }^k)}$，其中${\pi }^k$是指将置换$\pi$应用$k$次得到的置换。

已知$P(2)=4$，$P(3)=780$，$P(4)=38810300$。

求$P(100)$，并对$({10}^9+7)$取余作为你的答案。

---