---

Problem 903

---

Total 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$$

Let $Q(n)$ be the sum $\sum _{\pi }\sum _{i=1}^{n!}\text{rank}({\pi }^i)$, where $\pi$ ranges over all permutations of $\{1,\dots ,n\}$, and ${\pi }^i$ is the permutation arising from applying $\pi$ $i$ times.

For example, $Q(2)=5$, $Q(3)=88$, $Q(6)=133103808$ and $Q(10)\equiv 468421536(\mathrm{mod}{10}^9+7)$.

Find $Q({10}^6)$. 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$$

令$Q(n)$等于如下求和$\sum _{\pi }\sum _{i=1}^{n!}\text{rank}({\pi }^i)$，其中$\pi$取遍$\{1,\dots ,n\}$的所有置换，${\pi }^i$是指将置换$\pi$应用$i$次得到的置换。

已知$Q(2)=5$，$Q(3)=88$，$Q(6)=133103808$，$Q(10)\equiv 468421536(\mathrm{mod}{10}^9+7)$。

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

---