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