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;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
const int inf = (int)1.01e9;
const long double eps = 1e-9;
const long double pi = acos((long double)-1.0);
const int mod = (int)1e9 + 7;
void add(int &x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}
int mult(int x, int y) { return (long long)x * y % mod; }
int myPower(int x, int pw) {
  int res = 1;
  for (; pw; pw >>= 1) {
    if (pw & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
  }
  return res;
}
void precalc() {}
const int maxn = (int)1e3 + 10;
int n;
vector<vector<int> > es;
int read() {
  if (scanf("%d", &n) < 1) {
    return 0;
  }
  es = vector<vector<int> >(n);
  for (int i = 0; i < n - 1; ++i) {
    int s, t;
    scanf("%d%d", &s, &t);
    --s, --t;
    es[s].push_back(t), es[t].push_back(s);
  }
  return 1;
}
int dist[maxn];
int dist1[maxn];
void dfs1(int v, int p) {
  for (int u : es[v]) {
    if (u == p) {
      continue;
    }
    dist[u] = dist[v] + 1;
    dfs1(u, v);
  }
}
int used[maxn];
int cnt[maxn];
void dfs2(int v, int p) {
  cnt[v] = 1;
  for (int u : es[v]) {
    if (u == p || used[u]) {
      continue;
    }
    dfs2(u, v);
    cnt[v] += cnt[u];
  }
}
int diam, D;
void adde(vector<vector<int> > &a) {
  int n = ((int)(a).size());
  for (int i = 0; i < n; ++i) {
    a[i].push_back(0);
  }
  a.push_back(vector<int>(n + 1, 0));
  for (int i = n - 1; i >= 0; --i) {
    for (int j = n - 1; j >= 0; --j) {
      int x = a[i][j];
      if (!x) {
        continue;
      }
      a[i][j] = 0;
      if (i + 1 <= D) {
        add(a[i + 1][j], x);
      }
      if (i + 1 <= D) {
        add(a[i][j + 1], x);
      }
    }
  }
}
void makesum(vector<vector<int> > &a) {
  for (int i = 0; i < ((int)(a).size()); ++i) {
    for (int j = 0; j < ((int)(a).size()); ++j) {
      int &res = a[i][j];
      if (i) {
        add(res, a[i - 1][j]);
        if (j) {
          add(res, mod - a[i - 1][j - 1]);
        }
      }
      if (j) {
        add(res, a[i][j - 1]);
      }
    }
  }
}
void makeone(vector<vector<int> > &a) {
  for (int i = ((int)(a).size()) - 1; i >= 0; --i) {
    for (int j = ((int)(a).size()) - 1; j >= 0; --j) {
      int &res = a[i][j];
      if (i) {
        add(res, mod - a[i - 1][j]);
        if (j) {
          add(res, a[i - 1][j - 1]);
        }
      }
      if (j) {
        add(res, mod - a[i][j - 1]);
      }
    }
  }
}
void update(vector<vector<int> > &a, vector<vector<int> > &b) {
  assert(((int)(a).size()) >= ((int)(b).size()));
  makesum(a);
  makesum(b);
  for (int i = 0; i < ((int)(a).size()); ++i) {
    for (int j = 0; j < ((int)(a).size()); ++j) {
      a[i][j] =
          mult(a[i][j],
               b[min(((int)(b).size()) - 1, i)][min(((int)(b).size()) - 1, j)]);
    }
  }
  makeone(a);
}
vector<vector<int> > *dfs3(int v, int p) {
  int u0 = -1;
  for (int u : es[v]) {
    if (u == p || used[u]) {
      continue;
    }
    if (u0 == -1 || cnt[u] > cnt[u0]) {
      u0 = u;
    }
  }
  if (u0 == -1) {
    return new vector<vector<int> >({{1}});
  }
  auto ans = dfs3(u0, v);
  adde(*ans);
  for (int u : es[v]) {
    if (u == p || u == u0 || used[u]) {
      continue;
    }
    auto got = dfs3(u, v);
    adde(*got);
    update(*ans, *got);
  }
  return ans;
}
int ans[maxn];
int adds[maxn];
void solve() {
  dist[0] = 0;
  dfs1(0, -1);
  int v = max_element(dist, dist + n) - dist;
  dist[v] = 0;
  dfs1(v, -1);
  int u = max_element(dist, dist + n) - dist;
  diam = dist[u];
  memcpy(dist1, dist, sizeof(dist[0]) * n);
  dist[u] = 0;
  dfs1(u, -1);
  D = (diam + 1) / 2;
  for (int i = 0; i < n; ++i) {
    used[i] = 0;
  }
  int vs[2];
  int k = 0;
  for (int i = 0; i < n; ++i) {
    if (dist[i] + dist1[i] == diam && abs(dist[i] - dist1[i]) <= 1) {
      vs[k++] = i;
      used[i] = 1;
    }
  }
  assert(1 <= k && k <= 2);
  for (int i = 0; i < k; ++i) {
    dfs2(i, -1);
  }
  int res = 0;
  if (k == 1) {
    dfs2(vs[0], -1);
    for (int i = 0; i <= D; ++i) {
      ans[i] = 1;
    }
    for (int u : es[vs[0]]) {
      auto &got = *dfs3(u, vs[0]);
      adde(got);
      for (int i = 0; i <= D; ++i) {
        adds[i] = 0;
      }
      for (int i = 0; i < ((int)(got).size()); ++i) {
        for (int j = 0; j < ((int)(got).size()); ++j) {
          int cur = got[i][j];
          if (!cur) {
            continue;
          }
          int l = i, r = D - j;
          if (l <= r) {
            add(adds[l], cur);
            add(adds[r + 1], mod - cur);
          }
        }
      }
      int bal = 0;
      for (int i = 0; i <= D; ++i) {
        add(bal, adds[i]);
        ans[i] = mult(ans[i], bal);
      }
    }
    for (int i = 0; i <= D; ++i) {
      add(res, ans[i]);
    }
  } else {
    auto &ans1 = *(dfs3(vs[0], -1));
    auto &ans2 = *(dfs3(vs[1], -1));
    assert(((int)(ans1).size()) == D &&
           ((int)(ans2).size()) == ((int)(ans1).size()));
    for (int i = 0; i < ((int)(ans1).size()); ++i) {
      add(res, mult(2, mult(ans1[i][D - 1 - i], ans2[i][D - 1 - i])));
      if (i) {
        add(res, mult(ans1[i][D - 1 - i], ans2[i][D - i]));
        add(res, mult(ans2[i][D - 1 - i], ans1[i][D - i]));
        add(res, mult(ans1[i][D - 1 - i], ans2[i - 1][D - i]));
        add(res, mult(ans2[i][D - 1 - i], ans1[i - 1][D - i]));
      }
      if (i < ((int)(ans1).size()) - 1) {
        add(res, mult(ans1[i][D - 1 - i], ans2[i + 1][D - 1 - i]));
        add(res, mult(ans2[i][D - 1 - i], ans1[i + 1][D - 1 - i]));
      }
    }
  }
  printf("%d\n", res);
}
int main() {
  precalc();
  while (1) {
    if (!read()) {
      break;
    }
    solve();
  }
  return 0;
}
