#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
string direc = "URDL";
const long long MOD2 = (long long)1000000007 * (long long)1000000007;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
vector<int> ps[200005];
int miu[200005], ni[200005], Ans;
void init() {
  miu[1] = 1;
  for (int i = 1; i < 200005; ++i)
    for (int j = i + i; j < 200005; j += i) {
      miu[j] -= miu[i];
    }
  for (int(i) = 1; (i) <= (int)(m); (i)++)
    for (int j = i; j <= m; j += i) ps[j].push_back(i);
  ni[0] = 1;
  ni[1] = fastPow(k, 1000000007 - 2);
  for (int i = 2; i < 200005; i++)
    ni[i] = (long long)ni[i - 1] * ni[1] % 1000000007;
}
int gab(int a, int b) {
  int ans = 0;
  for (int x : ps[b]) {
    long long z = (long long)a / x * miu[x] % 1000000007;
    if (z < 0) z += 1000000007;
    addmod(ans, z);
  }
  return ans;
}
void cal(int s, int d) {
  int s2 = s / d;
  int l = max(s2 - (n - 1) / d, 1), r = min((n - 1) / d, s2 - 1);
  if (r < l) return;
  int z = gab(r, s2) - gab(l - 1, s2);
  if (z < 0) z += 1000000007;
  addmod(Ans, (long long)ni[n - max(s - n, d)] * z % 1000000007);
}
void fmain(int tid) {
  scanf("%d%d", &n, &k);
  m = n << 1;
  init();
  for (int d = 1; d <= n; d++) {
    for (int s = d; s <= m; s += d) {
      cal(s, d);
    }
  }
  printf("%d\n", Ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

### Prompt

Your challenge is to write a CPP solution 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 T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
string direc = "URDL";
const long long MOD2 = (long long)1000000007 * (long long)1000000007;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
vector<int> ps[200005];
int miu[200005], ni[200005], Ans;
void init() {
  miu[1] = 1;
  for (int i = 1; i < 200005; ++i)
    for (int j = i + i; j < 200005; j += i) {
      miu[j] -= miu[i];
    }
  for (int(i) = 1; (i) <= (int)(m); (i)++)
    for (int j = i; j <= m; j += i) ps[j].push_back(i);
  ni[0] = 1;
  ni[1] = fastPow(k, 1000000007 - 2);
  for (int i = 2; i < 200005; i++)
    ni[i] = (long long)ni[i - 1] * ni[1] % 1000000007;
}
int gab(int a, int b) {
  int ans = 0;
  for (int x : ps[b]) {
    long long z = (long long)a / x * miu[x] % 1000000007;
    if (z < 0) z += 1000000007;
    addmod(ans, z);
  }
  return ans;
}
void cal(int s, int d) {
  int s2 = s / d;
  int l = max(s2 - (n - 1) / d, 1), r = min((n - 1) / d, s2 - 1);
  if (r < l) return;
  int z = gab(r, s2) - gab(l - 1, s2);
  if (z < 0) z += 1000000007;
  addmod(Ans, (long long)ni[n - max(s - n, d)] * z % 1000000007);
}
void fmain(int tid) {
  scanf("%d%d", &n, &k);
  m = n << 1;
  init();
  for (int d = 1; d <= n; d++) {
    for (int s = d; s <= m; s += d) {
      cal(s, d);
    }
  }
  printf("%d\n", Ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

```