Problem 903

Total Permutation Powers

A permutation $\pi$ of $\{1, \dots, n\}$ can be represented in one-line notation as $\pi(1),\ldots,\pi(n) $. If all $n!$ permutations are written in lexicographic order then $\textrm{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, 3\quad 1, 3, 2 \quad 2, 1, 3 \quad 2, 3, 1 \quad 3, 1, 2 \quad 3, 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 \pmod {10^9 + 7}$.

Find $Q(10^6)$. Give your answer modulo $(10^9 + 7)$.

所有置换的幂

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

例如，$\text{rank}(2,1,3) = 3$，因为$\{1, 2, 3\}$的六个置换按字典序排列为：
$$1, 2, 3\quad 1, 3, 2 \quad 2, 1, 3 \quad 2, 3, 1 \quad 3, 1, 2 \quad 3, 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 \pmod {10^9 + 7}$。

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