给定 $n$，对于一个长度为 $n$，值域为 $n$ 的序列 $A$，按如下方法构造无限序列 $B_i(1 \le i \le n)$：

• $B_{i,1} = i$
• $B_{i,j} = A_{B_{i,j-1}}(j > 1)$

记 $S_i$ 为 $B_i$ 中只出现了一次的元素的个数，定义序列 $A$ 的价值为 $\sum_{i=1}^n S_i$，现在请求出所有 $n^n$ 个可能的序列 $A$ 的价值之和对 $M$ 取模的结果。

$n \le 2 \times 10^5, 10^8 \le M \le 10^9$.