#include <bits/stdc++.h>
using namespace std;
long long cc[400005], ans;
int u[400005], c, D[400005], n, i, j, cnt, x, y, d, is[400005], p[400005];
inline long long cal(int mx, int f1, int f2) {
  long long res = 0;
  for (int i = 2; i <= mx + mx; ++i)
    res += cc[max(f2, i * f1 - n)] * min(i - 1, mx + mx + 1 - i);
  return res % 1000000007;
}
long long ksm(long long x, long long y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x % 1000000007)
    if (y & 1) ret = ret * x % 1000000007;
  return ret;
}
int main() {
  cin >> n >> c;
  for (i = cc[0] = 1; i <= n + n; ++i) cc[i] = cc[i - 1] * c % 1000000007;
  for (i = 2, u[1] = D[1] = 1; i <= n; ++i) {
    if (!is[i]) p[++cnt] = i, D[i] = 2, u[i] = -1;
    for (j = 1; j <= cnt && (d = i * p[j]) < 400005; ++j) {
      is[d] = 1;
      if (i % p[j] == 0) {
        x = i / p[j];
        y = 3;
        while (x % p[j] == 0) x /= p[j], ++y;
        D[d] = D[x] * y;
        break;
      }
      D[d] = D[i] << 1;
      u[d] = -u[i];
    }
  }
  int h = n - 1;
  for (i = 1; i <= h; ++i)
    for (x = h / i, j = 1; j <= x; ++j) ans += u[j] * cal(x / j, i * j, i);
  cout << (ans % 1000000007 + 1000000007) * ksm(cc[n], 1000000007 - 2) %
              1000000007;
}

### Prompt

Please create a solution in cpp to the following problem:

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≤ 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 P/Q, where P and Q are coprime and Q isn't divided by 10^9 + 7. Output P⋅ Q^{-1} mod 10^9 + 7.

Input

The first and the only line contains two integers n, k (1≤ n ≤ 10^5, 1≤ k≤ 10^9) — the length of a string and the size of alphabet respectively.

Output

Output a single integer — P× Q^{-1} mod 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 1/3.

In the third example, there is only one such word, and it has beauty 99, so the average value is 99^2.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long cc[400005], ans;
int u[400005], c, D[400005], n, i, j, cnt, x, y, d, is[400005], p[400005];
inline long long cal(int mx, int f1, int f2) {
  long long res = 0;
  for (int i = 2; i <= mx + mx; ++i)
    res += cc[max(f2, i * f1 - n)] * min(i - 1, mx + mx + 1 - i);
  return res % 1000000007;
}
long long ksm(long long x, long long y) {
  long long ret = 1;
  for (; y; y >>= 1, x = x * x % 1000000007)
    if (y & 1) ret = ret * x % 1000000007;
  return ret;
}
int main() {
  cin >> n >> c;
  for (i = cc[0] = 1; i <= n + n; ++i) cc[i] = cc[i - 1] * c % 1000000007;
  for (i = 2, u[1] = D[1] = 1; i <= n; ++i) {
    if (!is[i]) p[++cnt] = i, D[i] = 2, u[i] = -1;
    for (j = 1; j <= cnt && (d = i * p[j]) < 400005; ++j) {
      is[d] = 1;
      if (i % p[j] == 0) {
        x = i / p[j];
        y = 3;
        while (x % p[j] == 0) x /= p[j], ++y;
        D[d] = D[x] * y;
        break;
      }
      D[d] = D[i] << 1;
      u[d] = -u[i];
    }
  }
  int h = n - 1;
  for (i = 1; i <= h; ++i)
    for (x = h / i, j = 1; j <= x; ++j) ans += u[j] * cal(x / j, i * j, i);
  cout << (ans % 1000000007 + 1000000007) * ksm(cc[n], 1000000007 - 2) %
              1000000007;
}

```