There is a tree T with N vertices, numbered 1 through N. For each 1 ≤ i ≤ N - 1, the i-th edge connects vertices a_i and b_i.

Snuke is constructing a directed graph T' by arbitrarily assigning direction to each edge in T. (There are 2^{N - 1} different ways to construct T'.)

For a fixed T', we will define d(s,\ t) for each 1 ≤ s,\ t ≤ N, as follows:

* d(s,\ t) = (The number of edges that must be traversed against the assigned direction when traveling from vertex s to vertex t)



In particular, d(s,\ s) = 0 for each 1 ≤ s ≤ N. Also note that, in general, d(s,\ t) ≠ d(t,\ s).

We will further define D as the following:

3d2f3f88e8fa23f065c04cd175c14ebf.png

Snuke is constructing T' so that D will be the minimum possible value. How many different ways are there to construct T' so that D will be the minimum possible value, modulo 10^9 + 7?

Constraints

* 2 ≤ N ≤ 1000
* 1 ≤ a_i,\ b_i ≤ N
* The given graph is a tree.

Input

The input is given from Standard Input in the following format:


N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}


Output

Print the number of the different ways to construct T' so that D will be the minimum possible value, modulo 10^9 + 7.

Examples

Input

4
1 2
1 3
1 4


Output

2


Input

4
1 2
2 3
3 4


Output

6


Input

6
1 2
1 3
1 4
2 5
2 6


Output

14


Input

10
2 4
2 5
8 3
10 7
1 6
2 8
9 5
8 6
10 6


Output

102
#include <bits/stdc++.h>

using namespace std;

const int md = 1000000007;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) {
    a -= md;
  }
}

inline int mul(int a, int b) {
  return (long long) a * b % md;
}

const int N = 2010;

int depth[N];
vector <int> g[N], new_g[N];
int it;
map <int, int> f[N][N];
int D;

int go(int v, int pr, int x) {
  if (f[v][x].find(D) != f[v][x].end()) {
    return f[v][x][D];
  }
  int &res = f[v][x][D];
  res = 1;
  int y = (D - depth[v]) - x;
//  cerr << "go " << v << " " << x << " " << y << endl;
  int sz = g[v].size();
  for (int j = 0; j < sz; j++) {
    int u = g[v][j];
    if (u == pr) {
      continue;
    }
    int cur = 0;
    if (x > 0) {
      cur = go(u, v, x - 1);
    }
    if (y > 0) {
      add(cur, go(u, v, x));
    }
    res = mul(res, cur);
  }
  return res;
}

int curr[N][N];
int x[N], d[N];
int C[N][N];
pair <int, int> edge[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int foo, bar;
    scanf("%d %d", &foo, &bar);
    foo--; bar--;
    edge[i] = make_pair(foo, bar);
    g[foo].push_back(bar);
    g[bar].push_back(foo);
  }
  int max_deg = 0;
  for (int i = 0; i < n; i++) {
    max_deg = max(max_deg, (int) g[i].size());
  }
  if (max_deg <= 2) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (j == 0) C[i][j] = 1; else
        if (i == 0) C[i][j] = 0;
        else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % md;
      }
    }
    int ans = C[n - 1][(n - 1) / 2];
    if (n % 2 == 0) {
      add(ans, ans);
    }
    printf("%d\n", ans);
    return 0;
  }
  int coeff = 1;
  int root;
  int another_root;
  int diam = 0;
  while (true) {
    D = (int) 1e9;
    root = -1;
    another_root = -1;
    for (int start = 0; start < n; start++) {
      for (int i = 0; i < n; i++) {
        d[i] = -1;
      }
      int b = 0, e = 1;
      x[0] = start;
      d[start] = 0;
      while (b < e) {
        int sz = g[x[b]].size();
        for (int j = 0; j < sz; j++) {
          int u = g[x[b]][j];
          if (d[u] == -1) {
            x[e] = u;
            d[u] = d[x[b]] + 1;
            e++;
          }
        }
        b++;
      }
      int rad = 0;
      for (int i = 0; i < n; i++) {
        rad = max(rad, d[i]);
      }
      diam = max(diam, rad);
      if (rad < D) {
        D = rad;
        root = start;
        another_root = -1;
        for (int i = 0; i < n; i++) {
          depth[i] = d[i];
        }
      } else {
        if (rad == D) {
          another_root = start;
        }
      }
    }
    if (diam % 2 == 0) {
      break;
    }
    coeff = mul(coeff, 2);
    break;
/*    assert(another_root != -1);
    for (int i = 0; i < n - 1; i++) {
      new_g[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
      int foo = edge[i].first;
      int bar = edge[i].second;
      if (foo == another_root) {
        foo = root;
      }
      if (bar == another_root) {
        bar = root;
      }
      if (foo == n - 1) {
        foo = another_root;
      }
      if (bar == n - 1) {
        bar = another_root;
      }
      new_g[foo].push_back(bar);
      new_g[bar].push_back(foo);
    }
    n--;
    for (int i = 0; i < n; i++) {
      g[i] = new_g[i];
    }*/
  }
//  cerr << "D = " << D << endl;
//  cerr << "diam = " << diam << endl;
//  cerr << "root = " << root << endl;
//  cerr << "another_root = " << another_root << endl;
  int ans = 0;
  if (diam % 2 == 0) {
    for (int x = 0; x <= D; x++) {
      int cur = go(root, another_root, x);
      add(ans, cur);
    }
  } else {
    for (int x = 0; x <= D; x++) {
      for (int y = 0; x + y <= D; y++) {
        if (x + y < D - 1) {
          continue;
        }
        bool flag = false;
        if (x + y < D) {
          D--;
          flag = true;
        }
        D++;
        int cur = go(another_root, root, x);
        curr[x][y] = cur;
        D--;
        if (flag) {
          D++;
        } else {
          if (x > 0) {
            add(cur, md - curr[x - 1][y]);
          }
          if (y > 0) {
            add(cur, md - curr[x][y - 1]);
          }
        }
//        cerr << "now cur = " << cur << endl;
        int new_x = x + 1;
        int new_y = y;
        int bound_x = D - new_y;
        int bound_y = D - new_x;
        int new_D = bound_x + bound_y;
        int old_D = D;
        D = new_D;
        cur = mul(cur, go(root, another_root, bound_x));
        add(ans, cur);
        D = old_D;
//        cerr << x << " " << y << " -> " << cur << endl;
      }
    }
  }
  printf("%d\n", mul(ans, coeff));
//  cerr << clock() << " ms" << endl;
  return 0;
}
