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;
typedef bool boolean;

#define ll long long

void exgcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}

int inv(int a, int n) {
  int x, y;
  exgcd(a, n, x, y);
  return (x < 0) ? (x + n) : (x);
}

const int Mod = 1e9 + 7;

template <const int Mod = :: Mod>
class Z {
  public:
    int v;

    Z() : v(0) {	}
    Z(int x) : v(x){	}
    Z(ll x) : v(x % Mod) {	}

    friend Z operator + (const Z& a, const Z& b) {
      int x;
      return Z(((x = a.v + b.v) >= Mod) ? (x - Mod) : (x));
    }
    friend Z operator - (const Z& a, const Z& b) {
      int x;
      return Z(((x = a.v - b.v) < 0) ? (x + Mod) : (x));
    }
    friend Z operator * (const Z& a, const Z& b) {
      return Z(a.v * 1ll * b.v);
    }
    friend Z operator ~(const Z& a) {
      return inv(a.v, Mod);
    }
    friend Z operator - (const Z& a) {
      return Z(0) - a;
    }
    Z& operator += (Z b) {
      return *this = *this + b;
    }
    Z& operator -= (Z b) {
      return *this = *this - b;
    }
    Z& operator *= (Z b) {
      return *this = *this * b;
    }
    friend boolean operator == (const Z& a, const Z& b) {
      return a.v == b.v;
    } 
};

Z<> qpow(Z<> a, int p) {
  Z<> rt = Z<>(1), pa = a;
  for ( ; p; p >>= 1, pa = pa * pa) {
    if (p & 1) {
      rt = rt * pa;
    }
  }
  return rt;
}

typedef Z<> Zi;

const int N = 1e3 + 5;

int n;
int L = -1, D;
vector<int> G[N];
Zi g[N][N], fl[N], fr[N], _g[N], h[N];

void find_far(int p, int fa, int d, int& mxd, int& id) {
  if (d > mxd) {
    mxd = d;
    id = p;
  }
  for (auto e : G[p]) {
    if (e ^ fa) {
      find_far(e, p, d + 1, mxd, id);
    }
  }
}

int da, db;
void get_diameter() {
  int mxd = -1;
  find_far(1, 0, 0, mxd, da);
  find_far(da, 0, 0, L, db);
  D = (L + 1) >> 1;
}

bool ind[N];
vector<int> dia;
void get_chain(int p, int fa) {
  dia.push_back(p);
  if (p == db) {
    throw 1;
  }
  for (auto e : G[p]) {
    if (e ^ fa) {
      get_chain(e, p);
    }
  }
  dia.pop_back();
}

void dfs(int p, int fa, int l, int lmx) {
  for (auto e : G[p]) {
    if (e ^ fa) {
      dfs(e, p, l - 1, lmx);
    }
  }
  for (int i = 0; i <= lmx; i++) {
    Zi f1 = (!!i), f2 = (i < l);
    if (f1.v) {
      for (auto e : G[p]) {
        if (e ^ fa) {
          f1 *= g[e][i - 1];
        }
      }
    }
    if (f2.v) {
      for (auto e : G[p]) {
        if (e ^ fa) {
          f2 *= g[e][i];
        }
      }
    }
    g[p][i] = f1 + f2;
  }
}

Zi work_odd() {
  for (int i = 1; i <= n; i++) {
    fill(g[i], g[i] + n + 2, Zi(0));
  }
  Zi ret = 0;
  g[dia[0]][0] = 1;
  fill(fl, fl + n + 2, Zi(0));
  for (int i = 1; i < D; i++) {
    int ls = dia[i - 1], p = dia[i];
    for (int j = 0; j < i; j++) {
      g[p][j + 1] += g[ls][j];
      g[p][j] += g[ls][j];
    }
    for (int j = i; j; j--) {
      fl[j] += fl[j - 1];
    }
    for (auto e : G[p]) {
      if (!ind[e]) {
        int l = i;
        dfs(e, p, l, l);
        copy(g[p], g[p] + l + 1, _g);
        copy(g[e], g[e] + l + 1, h);
        for (int j = 0; j <= l; j++) {
          g[p][j] *= g[e][j];
        }
        dfs(e, p, l + 1, l);
        for (int j = 0; j <= l; j++) {
          fl[j] = fl[j] * g[e][j] + _g[j] * (g[e][j] - h[j]);
        }
      }
    }
  }
  g[dia[L]][0] = 1;
  fill(fr, fr + n + 2, Zi(0));
  for (int i = L - 1; i >= D; i--) {
    int ls = dia[i + 1], p = dia[i];
    for (int j = 0; j < L - i; j++) {
      g[p][j + 1] += g[ls][j];
      g[p][j] += g[ls][j];
    }
    for (int j = L - i; j; j--) {
      fr[j] += fr[j - 1];
    }
    for (auto e : G[p]) {
      if (!ind[e]) {
        int l = L - i;
        dfs(e, p, l, l);
        copy(g[p], g[p] + l + 1, _g);
        copy(g[e], g[e] + l + 1, h);
        for (int j = 0; j <= l; j++) {
          g[p][j] *= g[e][j];
        }
        dfs(e, p, l + 1, l + 1);
        for (int j = 0; j <= l; j++) {
          fr[j] = fr[j] * g[e][j + 1] + _g[j] * (g[e][j + 1] - h[j]);
        }
      }
    }
  }
  int x = dia[D - 1], y = dia[D];
  for (int j = 0; j <= L; j++) {
    ret += (g[x][j] + fl[j]) * (g[y][j] + fr[j]) - fl[j] * fr[j];
  }
  for (int i = 1; i <= n; i++) {
    fill(g[i], g[i] + n + 2, Zi(0));
  }
  g[dia[0]][0] = 1;
  fill(fl, fl + n + 2, Zi(0));
  for (int i = 1; i < D; i++) {
    int ls = dia[i - 1], p = dia[i];
    for (int j = 0; j < i; j++) {
      g[p][j + 1] += g[ls][j];
      g[p][j] += g[ls][j];
    }
    for (int j = i; j; j--) {
      fl[j] += fl[j - 1];
    }
    for (auto e : G[p]) {
      if (!ind[e]) {
        int l = i;
        dfs(e, p, l, l);
        copy(g[p], g[p] + l + 1, _g);
        copy(g[e], g[e] + l + 1, h);
        for (int j = 0; j <= l; j++) {
          g[p][j] *= g[e][j];
        }
        dfs(e, p, l + 1, l + 1);
        for (int j = 0; j <= l; j++) {
          fl[j] = fl[j] * g[e][j + 1] + _g[j] * (g[e][j + 1] - h[j]);
        }
      }
    }
  }
  g[dia[L]][0] = 1;
  fill(fr, fr + n + 2, Zi(0));
  for (int i = L - 1; i >= D; i--) {
    int ls = dia[i + 1], p = dia[i];
    for (int j = 0; j < L - i; j++) {
      g[p][j + 1] += g[ls][j];
      g[p][j] += g[ls][j];
    }
    for (int j = L - i; j; j--) {
      fr[j] += fr[j - 1];
    }
    for (auto e : G[p]) {
      if (!ind[e]) {
        int l = L - i;
        dfs(e, p, l, l);
        copy(g[p], g[p] + l + 1, _g);
        copy(g[e], g[e] + l + 1, h);
        for (int j = 0; j <= l; j++) {
          g[p][j] *= g[e][j];
        }
        dfs(e, p, l + 1, l);
        for (int j = 0; j <= l; j++) {
          fr[j] = fr[j] * g[e][j] + _g[j] * (g[e][j] - h[j]);
        }
      }
    }
  }
  for (int j = 0; j <= L; j++) {
    ret += (g[x][j] + fl[j]) * (g[y][j + 1] + fr[j + 1]) - fl[j] * fr[j + 1];
  }
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 1, u, v; i < n; i++) {
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  get_diameter();
  try { get_chain(da, 0); } catch(int) {  }
  for (auto p : dia) {
    ind[p] = true;
  }
  Zi ans = 0;
  if (!L) {
    ans = 1;
  } else if (L & 1) {
    ans = work_odd() * 2;
  } else {
    g[dia[0]][0] = 1;
    for (int i = 1; i <= D; i++) {
      int ls = dia[i - 1], p = dia[i];
      for (int j = 0; j < i; j++) {
        g[p][j + 1] += g[ls][j];
        g[p][j] += g[ls][j];
      }
      for (auto e : G[p]) {
        if (!ind[e]) {
          dfs(e, p, i, i);
          for (int j = 0; j <= i; j++) {
            g[p][j] *= g[e][j];
          }
        }
      }
    }
    g[dia[L]][0] = 1;
    for (int i = L - 1; i > D; i--) {
      int ls = dia[i + 1], p = dia[i];
      for (int j = 0; j < L - i; j++) {
        g[p][j + 1] += g[ls][j];
        g[p][j] += g[ls][j];
      }
      for (auto e : G[p]) {
        if (!ind[e]) {
          dfs(e, p, L - i, L - i);
          for (int j = 0; j <= L - i; j++) {
            g[p][j] *= g[e][j];
          }
        }
      }
    }
    int x = dia[D], y = dia[D + 1];
    for (int j = 0; j <= L; j++) {
      ans += g[x][j] * g[y][j];
      if (j) {
        ans += g[x][j] * g[y][j - 1];
      }
    }
  }
  printf("%d\n", ans.v);
  return 0;
}
