Expected Value Again

4000ms

262144K

Description:

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

Input:

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:

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

Sample Input:

2 3

Sample Output:

333333336

Sample Input:

1 5

Sample Output:

Sample Input:

100 1

Sample Output:

Sample Input:

10 10

Sample Output:

412377396

Note:

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

Informação

Provedor Codeforces

Código CF1205E