#include <bits/stdc++.h>
using namespace std;
template <typename tp>
inline void read(tp &x) {
  x = 0;
  char c = getchar();
  int f = 0;
  for (; c < '0' || c > '9'; f |= c == '-', c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar())
    ;
  if (f) x = -x;
}
namespace {
const int mo = 1e9 + 7;
inline int add(int x, int y) {
  x += y;
  return x >= mo ? x - mo : x;
}
inline int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + mo : x;
}
inline int mul(int x, int y) { return (long long)x * y % mo; }
inline int power(int a, int k = mo - 2) {
  k %= mo - 1;
  if (k < 0) k += mo - 1;
  int ans = 1;
  for (; k; k >>= 1, a = mul(a, a))
    if (k & 1) ans = mul(ans, a);
  return ans;
}
}  // namespace
const int N = 3e5 + 233;
int n, k;
int np[N], mu[N], p[N], p_cnt;
vector<int> factor[N];
inline void prepare(int n) {
  np[1] = true;
  mu[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!np[i]) p[++p_cnt] = i, mu[i] = -1;
    for (int j = 1; j <= p_cnt && p[j] * i <= n; j++) {
      np[p[j] * i] = true;
      if (i % p[j] == 0)
        break;
      else
        mu[i * p[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i) factor[j].push_back(i);
}
inline int F(int s, int d) {
  int l = max(1, s / d - (n - 1) / d);
  int r = min((n - 1) / d, s / d - 1);
  if (l > r) return 0;
  assert(0 <= l && l <= r && r <= s);
  int ans = 0;
  for (auto e : factor[s / d]) {
    ans = add(ans, mul(mu[e], r / e - (l - 1) / e));
  }
  return ans;
}
int main(void) {
  read(n);
  read(k);
  prepare(2 * n);
  int ans = 0;
  for (int s = 2 * 1; s <= 2 * (n - 1); s++)
    for (auto d : factor[s]) {
      ans = add(ans, mul(F(s, d), power(k, max(d, s - n) - n)));
    }
  cout << ans << "\n";
}

### 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;
template <typename tp>
inline void read(tp &x) {
  x = 0;
  char c = getchar();
  int f = 0;
  for (; c < '0' || c > '9'; f |= c == '-', c = getchar())
    ;
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar())
    ;
  if (f) x = -x;
}
namespace {
const int mo = 1e9 + 7;
inline int add(int x, int y) {
  x += y;
  return x >= mo ? x - mo : x;
}
inline int sub(int x, int y) {
  x -= y;
  return x < 0 ? x + mo : x;
}
inline int mul(int x, int y) { return (long long)x * y % mo; }
inline int power(int a, int k = mo - 2) {
  k %= mo - 1;
  if (k < 0) k += mo - 1;
  int ans = 1;
  for (; k; k >>= 1, a = mul(a, a))
    if (k & 1) ans = mul(ans, a);
  return ans;
}
}  // namespace
const int N = 3e5 + 233;
int n, k;
int np[N], mu[N], p[N], p_cnt;
vector<int> factor[N];
inline void prepare(int n) {
  np[1] = true;
  mu[1] = 1;
  for (int i = 2; i <= n; i++) {
    if (!np[i]) p[++p_cnt] = i, mu[i] = -1;
    for (int j = 1; j <= p_cnt && p[j] * i <= n; j++) {
      np[p[j] * i] = true;
      if (i % p[j] == 0)
        break;
      else
        mu[i * p[j]] = -mu[i];
    }
  }
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i) factor[j].push_back(i);
}
inline int F(int s, int d) {
  int l = max(1, s / d - (n - 1) / d);
  int r = min((n - 1) / d, s / d - 1);
  if (l > r) return 0;
  assert(0 <= l && l <= r && r <= s);
  int ans = 0;
  for (auto e : factor[s / d]) {
    ans = add(ans, mul(mu[e], r / e - (l - 1) / e));
  }
  return ans;
}
int main(void) {
  read(n);
  read(k);
  prepare(2 * n);
  int ans = 0;
  for (int s = 2 * 1; s <= 2 * (n - 1); s++)
    for (auto d : factor[s]) {
      ans = add(ans, mul(F(s, d), power(k, max(d, s - n) - n)));
    }
  cout << ans << "\n";
}

```