E. Expected Value Againtime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputOutput a single integer — P\times Q^{-1} \bmod 10^9 + 7.ExamplesInput
2 3
Output
333333336
Input
1 5
Output
0
Input
100 1
Output
9801
Input
10 10
Output
412377396
NoteIn 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.
2 3

333333336 
['combinatorics', 'strings', '*3100']