#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 5;
int n, k;
vector<int> g[MAX];
long long sol;
struct data {
  long long s;
  int rem[5];
  data() {
    s = 0;
    for (int i = 0; i < 5; i++) rem[i] = 0;
  }
} up, dp[MAX];
data merge(const data &a, const data &b) {
  data c;
  c.s = a.s + b.s;
  for (int i = 0; i < 5; i++) c.rem[i] = a.rem[i] + b.rem[i];
  return c;
}
void dfs1(int u, int p = -1) {
  dp[u].s = 0;
  dp[u].rem[0] = 1;
  for (int v : g[u]) {
    if (v != p) {
      dfs1(v, u);
      dp[u].s += dp[v].s + dp[v].rem[0];
      for (int i = 0; i < k; i++) dp[u].rem[i] += dp[v].rem[(i - 1 + k) % k];
    }
  }
}
void dfs2(int u, int p, data up) {
  sol += up.s + dp[u].s;
  vector<data> pref;
  vector<int> sons;
  for (int i = 0; i < (int)g[u].size(); i++) {
    int v = g[u][i];
    if (v == p) continue;
    sons.push_back(v);
    if (pref.empty())
      pref.push_back(dp[v]);
    else
      pref.push_back(merge(pref.back(), dp[v]));
  }
  vector<data> suff(sons.size());
  for (int i = (int)sons.size() - 1; i >= 0; i--) {
    int v = sons[i];
    if (i == (int)sons.size() - 1)
      suff[i] = dp[v];
    else
      suff[i] = merge(suff[i + 1], dp[v]);
  }
  for (int i = 0; i < (int)sons.size(); i++) {
    int v = sons[i];
    data x, y;
    if (i > 0) x = pref[i - 1];
    if (i < (int)sons.size() - 1) y = suff[i + 1];
    data tmp = merge(x, y);
    tmp.s += up.s + tmp.rem[0];
    data ot = tmp;
    for (int j = 0; j < k; j++)
      tmp.rem[j] = up.rem[j] + ot.rem[(j - 1 + k) % k];
    tmp.rem[0]++;
    data nup;
    nup.s = tmp.s + tmp.rem[0];
    for (int j = 0; j < k; j++) nup.rem[j] = tmp.rem[(j - 1 + k) % k];
    dfs2(v, u, nup);
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs1(1);
  data x;
  dfs2(1, -1, x);
  printf("%lld\n", sol / 2);
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

A tree is an undirected connected graph without cycles. The distance between two vertices is the number of edges in a simple path between them.

Limak is a little polar bear. He lives in a tree that consists of n vertices, numbered 1 through n.

Limak recently learned how to jump. He can jump from a vertex to any vertex within distance at most k.

For a pair of vertices (s, t) we define f(s, t) as the minimum number of jumps Limak needs to get from s to t. Your task is to find the sum of f(s, t) over all pairs of vertices (s, t) such that s < t.

Input

The first line of the input contains two integers n and k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ 5) — the number of vertices in the tree and the maximum allowed jump distance respectively.

The next n - 1 lines describe edges in the tree. The i-th of those lines contains two integers ai and bi (1 ≤ ai, bi ≤ n) — the indices on vertices connected with i-th edge.

It's guaranteed that the given edges form a tree.

Output

Print one integer, denoting the sum of f(s, t) over all pairs of vertices (s, t) such that s < t.

Examples

Input

6 2
1 2
1 3
2 4
2 5
4 6


Output

20


Input

13 3
1 2
3 2
4 2
5 2
3 6
10 6
6 7
6 13
5 8
5 9
9 11
11 12


Output

114


Input

3 5
2 1
3 1


Output

3

Note

In the first sample, the given tree has 6 vertices and it's displayed on the drawing below. Limak can jump to any vertex within distance at most 2. For example, from the vertex 5 he can jump to any of vertices: 1, 2 and 4 (well, he can also jump to the vertex 5 itself).

<image>

There are <image> pairs of vertices (s, t) such that s < t. For 5 of those pairs Limak would need two jumps: (1, 6), (3, 4), (3, 5), (3, 6), (5, 6). For other 10 pairs one jump is enough. So, the answer is 5·2 + 10·1 = 20.

In the third sample, Limak can jump between every two vertices directly. There are 3 pairs of vertices (s < t), so the answer is 3·1 = 3.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 5;
int n, k;
vector<int> g[MAX];
long long sol;
struct data {
  long long s;
  int rem[5];
  data() {
    s = 0;
    for (int i = 0; i < 5; i++) rem[i] = 0;
  }
} up, dp[MAX];
data merge(const data &a, const data &b) {
  data c;
  c.s = a.s + b.s;
  for (int i = 0; i < 5; i++) c.rem[i] = a.rem[i] + b.rem[i];
  return c;
}
void dfs1(int u, int p = -1) {
  dp[u].s = 0;
  dp[u].rem[0] = 1;
  for (int v : g[u]) {
    if (v != p) {
      dfs1(v, u);
      dp[u].s += dp[v].s + dp[v].rem[0];
      for (int i = 0; i < k; i++) dp[u].rem[i] += dp[v].rem[(i - 1 + k) % k];
    }
  }
}
void dfs2(int u, int p, data up) {
  sol += up.s + dp[u].s;
  vector<data> pref;
  vector<int> sons;
  for (int i = 0; i < (int)g[u].size(); i++) {
    int v = g[u][i];
    if (v == p) continue;
    sons.push_back(v);
    if (pref.empty())
      pref.push_back(dp[v]);
    else
      pref.push_back(merge(pref.back(), dp[v]));
  }
  vector<data> suff(sons.size());
  for (int i = (int)sons.size() - 1; i >= 0; i--) {
    int v = sons[i];
    if (i == (int)sons.size() - 1)
      suff[i] = dp[v];
    else
      suff[i] = merge(suff[i + 1], dp[v]);
  }
  for (int i = 0; i < (int)sons.size(); i++) {
    int v = sons[i];
    data x, y;
    if (i > 0) x = pref[i - 1];
    if (i < (int)sons.size() - 1) y = suff[i + 1];
    data tmp = merge(x, y);
    tmp.s += up.s + tmp.rem[0];
    data ot = tmp;
    for (int j = 0; j < k; j++)
      tmp.rem[j] = up.rem[j] + ot.rem[(j - 1 + k) % k];
    tmp.rem[0]++;
    data nup;
    nup.s = tmp.s + tmp.rem[0];
    for (int j = 0; j < k; j++) nup.rem[j] = tmp.rem[(j - 1 + k) % k];
    dfs2(v, u, nup);
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i < n; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dfs1(1);
  data x;
  dfs2(1, -1, x);
  printf("%lld\n", sol / 2);
  return 0;
}

```