#include <bits/stdc++.h>
using namespace std;
long long ksm(long long a, long long b) {
  if (!b) return 1;
  long long ns = ksm(a, b >> 1);
  ns = ns * ns % 1000000007;
  if (b & 1) ns = ns * a % 1000000007;
  return ns;
}
int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
int mn[200005];
int c(int u, int v) {
  if (v > 2 * u) return 0;
  if (v < 2) return 0;
  int bg = max(1, v - u), ed = min(u, v - 1);
  return ed - bg + 1;
}
int rm[200005];
int mu[200005];
int bpr[200005];
void gt(int q) {
  for (int i = 1; i <= 2 * q; i++) rm[i] = 0;
  for (int i = 1; i <= q; i++)
    if (mu[i]) {
      int dv = q / i;
      for (int s = 1; s <= 2 * dv; s++) rm[s * i] += mu[i] * c(dv, s);
    }
}
int main() {
  for (int i = 0; i < 200005; i++) bpr[i] = 1, mu[i] = 1;
  for (int i = 2; i < 200005; i++) {
    if (!bpr[i]) continue;
    for (int j = 1; j * i < 200005; j++) bpr[i * j] = 0, mu[i * j] *= -1;
    for (int j = 1; 1ll * j * i * i < 200005; j++) mu[j * i * i] = 0;
  }
  int n, k;
  cin >> n >> k;
  long long ans = 0;
  for (int i = 2; i <= 2 * n - 2; i++) mn[i] = c(n - 1, i);
  for (int i = 1; i < n; i++) {
    int q = (n - 1) / i;
    int cnt = 0;
    gt(q);
    for (int s = 1; s <= n / i + 1 && s <= 2 * q; s++) {
      int nr = rm[s];
      mn[i * s] -= nr;
      cnt = (cnt + nr) % 1000000007;
    }
    ans += 1ll * cnt * ksm(k, i) % 1000000007, ans %= 1000000007;
  }
  for (int i = n + 1; i <= 2 * n; i++) {
    ans += 1ll * mn[i] * ksm(k, i - n);
    ans %= 1000000007;
  }
  long long bk = ksm(ksm(k, n), 1000000007 - 2);
  ans = ans * bk % 1000000007;
  cout << ans << endl;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 ksm(long long a, long long b) {
  if (!b) return 1;
  long long ns = ksm(a, b >> 1);
  ns = ns * ns % 1000000007;
  if (b & 1) ns = ns * a % 1000000007;
  return ns;
}
int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
int mn[200005];
int c(int u, int v) {
  if (v > 2 * u) return 0;
  if (v < 2) return 0;
  int bg = max(1, v - u), ed = min(u, v - 1);
  return ed - bg + 1;
}
int rm[200005];
int mu[200005];
int bpr[200005];
void gt(int q) {
  for (int i = 1; i <= 2 * q; i++) rm[i] = 0;
  for (int i = 1; i <= q; i++)
    if (mu[i]) {
      int dv = q / i;
      for (int s = 1; s <= 2 * dv; s++) rm[s * i] += mu[i] * c(dv, s);
    }
}
int main() {
  for (int i = 0; i < 200005; i++) bpr[i] = 1, mu[i] = 1;
  for (int i = 2; i < 200005; i++) {
    if (!bpr[i]) continue;
    for (int j = 1; j * i < 200005; j++) bpr[i * j] = 0, mu[i * j] *= -1;
    for (int j = 1; 1ll * j * i * i < 200005; j++) mu[j * i * i] = 0;
  }
  int n, k;
  cin >> n >> k;
  long long ans = 0;
  for (int i = 2; i <= 2 * n - 2; i++) mn[i] = c(n - 1, i);
  for (int i = 1; i < n; i++) {
    int q = (n - 1) / i;
    int cnt = 0;
    gt(q);
    for (int s = 1; s <= n / i + 1 && s <= 2 * q; s++) {
      int nr = rm[s];
      mn[i * s] -= nr;
      cnt = (cnt + nr) % 1000000007;
    }
    ans += 1ll * cnt * ksm(k, i) % 1000000007, ans %= 1000000007;
  }
  for (int i = n + 1; i <= 2 * n; i++) {
    ans += 1ll * mn[i] * ksm(k, i - n);
    ans %= 1000000007;
  }
  long long bk = ksm(ksm(k, n), 1000000007 - 2);
  ans = ans * bk % 1000000007;
  cout << ans << endl;
  return 0;
}

```