Codeforces Round 580 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

strings

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Expected Value Again

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

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

Examples

Input

2 3

Output

333333336

Input

1 5

Output

0

Input

100 1

Output

9801

Input

10 10

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/29/2024 17:44:20 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|