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;
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;
using Graph = vector<vector<int>>;
struct Problem {
  LL n;
  Graph t;
  vector<int> height;
  vector<LL> fac, inv;
  Problem(LL n) : n(n), t(n), height(n), fac(2020), inv(2020){};
  int maxd, D;
  int bfs(int s) {
    vector<int> vis(n), ord;
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    ord.push_back(s);
    while (!Q.empty()) {
      int cur = Q.front();
      Q.pop();
      for (int v : t[cur]) {
        if (vis[v] == 0) {
          vis[v] = 1;
          Q.push(v);
          ord.push_back(v);
        }
      }
    }
    return ord.back();
  }
  int dfs_h(int par, int cur) {
    if ((int)t[cur].size() == 1 and t[cur][0] == par) {
      return height[cur] = 1;
    }
    int ret = 1;
    for (int v : t[cur]) {
      if (v != par) {
        ret = max(ret, dfs_h(cur, v) + 1);
      }
    }
    return height[cur] = ret;
  }
  inline void makesum(vector<vector<LL>> &vec) {
    for (int i = 0; i < (int)vec.size(); ++i) {
      for (int j = 1; j < (int)vec.size(); ++j) {
        vec[i][j] += vec[i][j - 1];
        if (vec[i][j] > MOD) vec[i][j] -= MOD;
      }
    }
    for (int j = 0; j < (int)vec.size(); ++j) {
      for (int i = 1; i < (int)vec.size(); ++i) {
        vec[i][j] += vec[i - 1][j];
        if (vec[i][j] > MOD) vec[i][j] -= MOD;
        ;
      }
    }
  }
  inline LL modcomb(int a, int b) {
    return (fac[a] * inv[b] % MOD) * inv[a - b] % MOD;
  }
  vector<vector<LL>> dfs(int par, int cur, int s = 1) {
    ;
    int sz = min(height[cur] + s + 1, D + 1);
    if ((int)t[cur].size() == 1 and t[cur][0] != par) {
      return dfs(cur, t[cur][0]);
    }
    if ((int)t[cur].size() == 2) {
      for (int v : t[cur]) {
        if (v != par) return dfs(cur, v, s + 1);
      }
    }
    vector<vector<LL>> ret(sz, vector<LL>(sz));
    ret[0][0] = 1;
    for (auto v : t[cur]) {
      if (v != par) {
        ;
        makesum(ret);
        vector<vector<LL>> tmp(sz, vector<LL>(sz));
        auto res = dfs(cur, v);
        for (int i = 0; i < (int)tmp.size(); ++i) {
          for (int j = 0; j < (int)tmp.size(); ++j) {
            if (i < (int)res.size() && j < (int)res.size()) {
              int ii = min({i, D - j}), jj = min({j, D - i});
              LL gp = res[i][j];
              if (i > 0) gp -= res[i - 1][j];
              if (j > 0) gp -= res[i][j - 1];
              if (i > 0 and j > 0) gp += res[i - 1][j - 1];
              if (ii > 0 and jj >= 0) tmp[i][j] += gp * ret[ii - 1][jj];
              if (ii >= 0 and jj > 0) tmp[i][j] += gp * ret[ii][jj - 1];
              if (ii > 0 and jj > 0) tmp[i][j] -= gp * ret[ii - 1][jj - 1];
            };
            {
              int ii = min({i, (int)res.size() - 1, D - j}),
                  jj = min({j, (int)res.size() - 1, D - i});
              LL gp = ret[i][j];
              if (i > 0) gp -= ret[i - 1][j];
              if (j > 0) gp -= ret[i][j - 1];
              if (i > 0 and j > 0) gp += ret[i - 1][j - 1];
              if (ii >= 0 and jj >= 0) tmp[i][j] += gp * res[ii][jj];
            };
            if (i + j <= D) {
              int ii = min(i - 1, (int)res.size() - 1);
              int jj = min(j - 1, (int)res.size() - 1);
              ;
              if (j < (int)res.size() and i > 0 and j > 0)
                tmp[i][j] +=
                    ((ret[i][j - 1] - ret[i - 1][j - 1] + MOD * 2) % MOD) *
                    ((res[ii][j] - res[ii][j - 1] + MOD * 2) % MOD);
              if (i < (int)res.size() and i > 0 and j > 0)
                tmp[i][j] +=
                    ((ret[i - 1][j] - ret[i - 1][j - 1] + MOD * 2) % MOD) *
                    ((res[i][jj] - res[i - 1][jj] + MOD * 2) % MOD);
            }
            tmp[i][j] = (tmp[i][j] % MOD + MOD) % MOD;
            ;
          }
        }
        ret = move(tmp);
      }
    };
    vector<vector<LL>> res(sz, vector<LL>(sz));
    for (int i = 0; i < (int)ret.size(); ++i) {
      for (int j = 0; j < (int)ret.size(); ++j) {
        for (int k = max(0, j + s - sz + 1); k < min(s + 1, sz - i); ++k) {
          res[i + k][j + s - k] += ret[i][j] * modcomb(s, k);
          res[i + k][j + s - k] = (res[i + k][j + s - k] % MOD + MOD) % MOD;
          ;
        }
      }
    };
    makesum(res);
    return res;
  }
  long long modpow(long long a, long long n, long long mod = MOD) {
    long long i = 1, ret = 1, p = a;
    while (i <= n) {
      if (i & n) ret = (ret * p) % mod;
      i = (i << 1);
      p = (p * p) % mod;
    }
    return ret;
  }
  void solve() {
    for (int i = 0; i < n - 1; ++i) {
      int a, b;
      cin >> a >> b;
      --a;
      --b;
      t[a].push_back(b);
      t[b].push_back(a);
    }
    fac[0] = 1;
    for (int i = 1; i < (int)fac.size(); ++i) {
      fac[i] = fac[i - 1] * i % MOD;
    }
    inv.back() = modpow(fac.back(), MOD - 2);
    for (int i = (int)fac.size() - 2; i >= 0; --i) {
      inv[i] = inv[i + 1] * (i + 1) % MOD;
    }
    int root = bfs(0);
    root = bfs(root);
    maxd = dfs_h(-1, root);
    D = (maxd) / 2;
    auto ans = dfs(-1, root);
    ;
    cout << ans[D][D] << "\n";
  }
};
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  long long n = 0;
  cin >> n;
  Problem p(n);
  p.solve();
  return 0;
}
