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.
import java.util.*;
import java.io.*;

public class TaskC {
	FastScanner in;
	PrintWriter out;

	public long dfs(int x, boolean[] used, ArrayList<Integer>[] a, int k,
			long[] jmp, long[][] jmpMd) {
		used[x] = true;
		long ans = 0;
		jmpMd[x][0] = 1;
		for (int y : a[x]) {
			if (!used[y]) {
				ans += dfs(y, used, a, k, jmp, jmpMd);

				long jmpN = jmp[y] + jmpMd[y][k - 1];
				for (int j = 0; j < k; j++) {
					ans += jmpMd[x][j] * jmpN;
					ans += jmpMd[y][j] * jmp[x];
					for (int jj = 0; jj < k; jj++) {
						ans += (jmpMd[x][j] * jmpMd[y][jj])
								* ((j + (jj + 1) % k) / k);
						if ((j + (jj + 1) % k) % k != 0) {
							ans += jmpMd[y][jj] * jmpMd[x][j];

						}
					}
				}
				jmp[x] += jmpN;

				for (int j = 0; j < k; j++) {
					jmpMd[x][(j + 1) % k] += jmpMd[y][j];
				}

			}
		}
		return ans;
	}

	public void solve() throws IOException {
		int n = in.nextInt();
		int k = in.nextInt();
		ArrayList<Integer>[] a = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			a[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < n - 1; i++) {
			int x = in.nextInt() - 1;
			int y = in.nextInt() - 1;
			a[x].add(y);
			a[y].add(x);
		}
		long[] jmp = new long[n];
		long[][] jmpMd = new long[n][k];
		boolean[] used = new boolean[n];
		System.out.println(dfs(0, used, a, k, jmp, jmpMd));

	}

	public void run() {
		try {
			in = new FastScanner(new InputStreamReader(System.in));
			out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
					System.out)));
			solve();
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		FastScanner(InputStreamReader isr) {
			br = new BufferedReader(isr);

		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}

	public static void main(String[] arg) {
		new TaskC().run();
	}
}