CF1205E.Expected Value Again

You are given integers $n$, $k$. Let's consider the alphabet consisting of $k$ different elements.

Let beauty $f(s)$ of the string $s$ be the number of indexes $i$, $1\le i \lt |s|$, for which prefix of $s$ of length $i$ equals to suffix of $s$ of length $i$. For example, beauty of the string $abacaba$ equals $2$, as for $i = 1, 3$ prefix and suffix of length $i$ are equal.

Consider all words of length $n$ in the given alphabet. Find the expected value of $f(s)^2$ of a uniformly chosen at random word. We can show that it can be expressed as $\frac{P}{Q}$, where $P$ and $Q$ are coprime and $Q$ isn't divided by $10^9 + 7$. Output $P\cdot Q^{-1} \bmod 10^9 + 7$.

给你两个整数 $n$ 和 $k$。考虑由 $k$ 个不同字符组成的字母表。

定义字符串 $s$ 的“优美度” $f(s)$ 为满足如下条件的下标 $i$ 的个数：$1 \le i < |s|$，且 $s$ 的长度为 $i$ 的前缀等于其长度为 $i$ 的后缀。例如，字符串 $abacaba$ 的优美度为 $2$，因为当 $i = 1$ 和 $i = 3$ 时，长度为 $i$ 的前缀与后缀相等。

考虑该字母表中所有长度为 $n$ 的字符串。求在所有这些字符串中均匀随机选取一个字符串 $s$ 时，$f(s)^2$ 的期望值。可以证明该期望值可表示为 $\frac{P}{Q}$，其中 $P$ 与 $Q$ 互质，且 $Q$ 不被 $10^9 + 7$ 整除。请输出 $P\cdot Q^{-1} \bmod 10^9 + 7$。

The first and the only line contains two integers $n$, $k$ ($1\le n \le 10^5$, $1\le k\le 10^9$) — the length of a string and the size of alphabet respectively.

第一行且唯一一行包含两个整数 $n$、$k$（$1\le n \le 10^5$，$1\le k\le 10^9$），分别表示字符串的长度和字母表的大小。

Output a single integer — $P\times Q^{-1} \bmod 10^9 + 7$.

输出一个整数——$P\times Q^{-1} \bmod 10^9 + 7$。

In the first example, there are $9$ words of length $2$ in alphabet of size $3$ — $aa$, $ab$, $ac$, $ba$, $bb$, $bc$, $ca$, $cb$, $cc$. $3$ of them have beauty $1$ and $6$ of them have beauty $0$, so the average value is $\frac{1}{3}$.

In the third example, there is only one such word, and it has beauty $99$, so the average value is $99^2$.

在第一个例子中，大小为 $3$ 的字母表中长度为 $2$ 的单词共有 $9$ 个——即 $aa$、$ab$、$ac$、$ba$、$bb$、$bc$、$ca$、$cb$、$cc$。其中 $3$ 个单词的“优美度”为 $1$，其余 $6$ 个单词的“优美度”为 $0$，因此平均值为 $\frac{1}{3}$。

在第三个例子中，满足条件的单词仅有一个，其“优美度”为 $99$，因此平均值为 $99^2$。