Expected Value Again

题意翻译

对于一个字符串$s$，我们定义其**美丽值**$f(s)$为满足下列两个条件的正整数$i$的个数： - $1\leq i<|s|$ - $s$长度为$i$的前缀与后缀相等，即$\forall j\in N,1\leq j\leq i$，均有$s_j=s_{|s|-i+j}$ 给定正整数$n(1\leq n\leq 10^5),k(1\leq k\leq 10^9)$。设字符集大小为$k$，请求出所有长度为$n$的字符串$s$的$f(s)^2$的期望值。

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

2 3

输出样例 #1

333333336

输入样例 #2

1 5

输出样例 #2

0

输入样例 #3

100 1

输出样例 #3

9801

输入样例 #4

10 10

输出样例 #4

412377396

说明

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

题意翻译

对于一个字符串$s$，我们定义其**美丽值**$f(s)$为满足下列两个条件的正整数$i$的个数： - $1\leq i<|s|$ - $s$长度为$i$的前缀与后缀相等，即$\forall j\in N,1\leq j\leq i$，均有$s_j=s_{|s|-i+j}$ 给定正整数$n(1\leq n\leq 10^5),k(1\leq k\leq 10^9)$。设字符集大小为$k$，请求出所有长度为$n$的字符串$s$的$f(s)^2$的期望值。