#include <bits/stdc++.h>
typedef struct nodo {
  int dato;
  struct nodo* siguiente;
} Nodo;
typedef Nodo* Arbol;
void insertar_nodo(int x, int y);
void recorrido(int a, int b);
long long int dis[50005][505];
Arbol CABEZA[100005];
int P[100005];
int k;
int main() {
  int i, j, n, x, y;
  long long int respuesta = 0, suma;
  Arbol arbol;
  scanf("%d %d", &n, &k);
  for (i = 0; i < n - 1; i++) {
    scanf("%d %d", &x, &y);
    insertar_nodo(x, y);
    insertar_nodo(y, x);
  }
  recorrido(1, 1);
  for (i = 1; i <= n; i++) {
    respuesta += dis[i][k];
    arbol = CABEZA[i];
    suma = 0;
    while (arbol) {
      for (j = 1; j < k && arbol->dato != P[i]; j++)
        suma += dis[arbol->dato][j - 1] *
                (dis[i][k - j] - dis[arbol->dato][k - j - 1]);
      arbol = arbol->siguiente;
    }
    respuesta += suma / 2;
  }
  printf("%I64d\n", respuesta);
  return 0;
}
void insertar_nodo(int a, int b) {
  Arbol arbol;
  arbol = (Arbol)malloc(sizeof(Nodo));
  arbol->dato = b;
  arbol->siguiente = CABEZA[a];
  CABEZA[a] = arbol;
}
void recorrido(int a, int b) {
  Arbol arbol;
  int i;
  P[a] = b;
  dis[a][0] = 1;
  for (arbol = CABEZA[a]; arbol != NULL; arbol = arbol->siguiente) {
    if (arbol->dato != b) {
      recorrido(arbol->dato, a);
      dis[a][1]++;
      for (i = 2; i <= k; i++) {
        dis[a][i] += dis[arbol->dato][i - 1];
      }
    }
  }
}

### Prompt

Please formulate a Cpp solution to the following problem:

A tree is a connected graph that doesn't contain any cycles.

The distance between two vertices of a tree is the length (in edges) of the shortest path between these vertices.

You are given a tree with n vertices and a positive number k. Find the number of distinct pairs of the vertices which have a distance of exactly k between them. Note that pairs (v, u) and (u, v) are considered to be the same pair.

Input

The first line contains two integers n and k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 500) — the number of vertices and the required distance between the vertices.

Next n - 1 lines describe the edges as "ai bi" (without the quotes) (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai and bi are the vertices connected by the i-th edge. All given edges are different.

Output

Print a single integer — the number of distinct pairs of the tree's vertices which have a distance of exactly k between them.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

5 2
1 2
2 3
3 4
2 5


Output

4


Input

5 3
1 2
2 3
3 4
4 5


Output

2

Note

In the first sample the pairs of vertexes at distance 2 from each other are (1, 3), (1, 5), (3, 5) and (2, 4).

### Response

```cpp
#include <bits/stdc++.h>
typedef struct nodo {
  int dato;
  struct nodo* siguiente;
} Nodo;
typedef Nodo* Arbol;
void insertar_nodo(int x, int y);
void recorrido(int a, int b);
long long int dis[50005][505];
Arbol CABEZA[100005];
int P[100005];
int k;
int main() {
  int i, j, n, x, y;
  long long int respuesta = 0, suma;
  Arbol arbol;
  scanf("%d %d", &n, &k);
  for (i = 0; i < n - 1; i++) {
    scanf("%d %d", &x, &y);
    insertar_nodo(x, y);
    insertar_nodo(y, x);
  }
  recorrido(1, 1);
  for (i = 1; i <= n; i++) {
    respuesta += dis[i][k];
    arbol = CABEZA[i];
    suma = 0;
    while (arbol) {
      for (j = 1; j < k && arbol->dato != P[i]; j++)
        suma += dis[arbol->dato][j - 1] *
                (dis[i][k - j] - dis[arbol->dato][k - j - 1]);
      arbol = arbol->siguiente;
    }
    respuesta += suma / 2;
  }
  printf("%I64d\n", respuesta);
  return 0;
}
void insertar_nodo(int a, int b) {
  Arbol arbol;
  arbol = (Arbol)malloc(sizeof(Nodo));
  arbol->dato = b;
  arbol->siguiente = CABEZA[a];
  CABEZA[a] = arbol;
}
void recorrido(int a, int b) {
  Arbol arbol;
  int i;
  P[a] = b;
  dis[a][0] = 1;
  for (arbol = CABEZA[a]; arbol != NULL; arbol = arbol->siguiente) {
    if (arbol->dato != b) {
      recorrido(arbol->dato, a);
      dis[a][1]++;
      for (i = 2; i <= k; i++) {
        dis[a][i] += dis[arbol->dato][i - 1];
      }
    }
  }
}

```