There are N towers in the town where Ikta lives. Each tower is given a different number from 0 to N-1, and the tower with number i is called tower i. Curious Ikta was interested in the height of the N towers and decided to make a table T showing the magnitude relationship between them. T has N × N elements, and each element Ti, j (0 ≤ i, j ≤ N − 1) is defined as follows.

* Ti, j = −1 ⇔ The height of tower i is smaller than the height of tower j
* Ti, j = 0 ⇔ The height of tower i is equal to the height of tower j
* Ti, j = 1 ⇔ The height of tower i is larger than the height of tower j



As a survey to create Table T, Ikta repeated N-1 times to select two towers and compare their heights.

We know the following about Ikta's investigation.

* If tower ai and tower bi were selected in the i-th comparison (1 ≤ i ≤ \ N − 1), the height of tower ai was larger than the height of tower bi. That is, Tai, bi = 1, Tbi, ai = −1.
* Each tower has been compared to a tower larger than itself at most once.



Unfortunately, it is not always possible to uniquely determine the contents of Table T based on the information obtained from Ikta's research. If the table T is consistent with Ikta's research and there is a combination of tower heights in which T is defined, we will call T the correct table. Please calculate how many kinds of correct tables you can think of and tell Ikta.

However, although the heights of the two towers compared are different from each other, not all towers are different from each other.



Input

The input is given in the following format.


N
a1 b1
...
aN−1 bN−1


N represents the number of towers. ai, bi (1 ≤ i ≤ N − 1) indicates that the tower ai is higher than the tower bi.

Constraints

Each variable being input satisfies the following constraints.

* 1 ≤ N ≤ 200
* 0 ≤ ai, bi <N
* ai ≠ bi
* Different towers may be the same height.
* Ikta's findings are not inconsistent, and there is at least one Table T that is consistent with Ikta's findings.

Output

Output the remainder of dividing the number of possible correct number of tables T by 1,000,000,007.

Examples

Input

3
0 1
1 2


Output

1


Input

3
0 1
0 2


Output

3


Input

1


Output

1


Input

7
0 1
1 2
2 3
3 4
0 5
0 6


Output

91
#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;

const int My_Inf=2147483647;
const long long int My_LInf=9223372036854775807;

const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,1,0,-1 };

map<char, int>mp;

struct aa {
	int y;
	int x;
	int time;
};
class Compare {
public:
	//aaが昇順に並ぶ
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};



const int mod = 1000000007;
struct Mod {
public:
	int num;
	Mod() : num(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) { ; }
	Mod(int n) : num((n % mod + mod) % mod) { ; }
	operator int() { return num; }
};

Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod mod_pow(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = mod_pow( (a * a) , (n / 2));
	if (n % 2) res = res * a;
	return res;
}
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
	assert(b.num != 0);
	return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) {
	assert(b.num != 0);
	return Mod(a) * inv(b);
}
Mod operator/=(Mod &a, const Mod b) {
	assert(b.num != 0);
	return a = a * inv(b);
}

#define MAX_MOD_N 1024000

Mod fact[MAX_MOD_N], factinv[MAX_MOD_N];
void init() {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < MAX_MOD_N - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
}
Mod comb(const int a, const int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}
struct Node {
	int id;
	int paid;
	vector<int>chid;
	Node(int a) :chid(){
		id = a;
		paid = -1;
	}
};
vector<Node>nodes;
map<int, Mod>getans(int nid) {
	if (nodes[nid].chid.size() == 0) {
		map<int, Mod>mp;
		mp[1] = 1;
		return mp;
	}
	else if (nodes[nid].chid.size() == 1) {
		map<int, Mod>mp(getans(nodes[nid].chid[0]));
		map<int, Mod>nmp;
		for (auto i : mp) {
			nmp[i.first + 1] = i.second;
		}
		return nmp;
	}
	else {
		map<int, Mod> now = getans(nodes[nid].chid[0]);
		for (int i = 1; i < nodes[nid].chid.size(); ++i) {
			map<int, Mod>next = getans(nodes[nid].chid[i]);
			map<int, Mod>newmap;
			for (auto j : now) {
				for (auto k : next) {
					pair< int, Mod>l(j);
					pair<int, Mod>r(k);
					if (l.first < r.first) {
						swap(l, r);
					}
					assert(l.first >= r.first);
					for (int sum = l.first; sum <= l.first + r.first; ++sum) {
						int kaburi = l.first + r.first - sum;
						int kaburazu = sum - l.first;
							
						Mod ans = comb(l.first, kaburi);
						ans *= comb(l.first + kaburazu, kaburazu);
						ans *= l.second*r.second;
						newmap[sum] += ans;
					}
					
				}
			}
			now = newmap;
		}
		map<int, Mod>nmp;
		for (auto i : now) {
			nmp[i.first + 1] = i.second;
		}
		return nmp;
	}
}
int main() {
	init();
	/*mp['L'] = 0;
	mp['D'] = 1;
	mp['R'] = 2;
	mp['U'] = 3;
	
	int W, H, N; cin >> W >> H >> N;
	int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy;
	vector<vector<int>>wedges(H + 1, vector<int>(W));
	vector<vector<int>>hedges(H, vector<int>(W + 1));

	for (int i = 0; i < N; ++i) {
		int x, y; cin >> x >> y;
		int atime; string st;
		cin >> atime >> st;
		for (int k = 0; k < atime; ++k) {
			for (int j = 0; j < st.size(); ++j) {
				int a = mp[st[j]];
				int ay = y + dy[a];
				int ax = x + dx[a];
				if (ay < 0 || ay >= H || ax < 0 || ax >= W) {
					
				}
				else {
					if (a % 2) {
						if (a == 1) {

							hedges[y+1][x]++;
						}
						else {
							hedges[y][x]++;

						}
					}
					else {
						if (a == 0) {

							wedges[y][x]++;
						}
						else {
							wedges[y][x+1]++;

						}
					}
					y = ay;
					x = ax;
				}

			}
		}
	}
	vector<vector<int>>mintime(H+1, vector<int>(W+1,100000000));
	mintime[sy][sx] = 0;
	priority_queue<aa, vector<aa>, Compare>que;
	que.push(aa{ sy, sx, 0 });
	while (!que.empty()) {
		aa atop(que.top());
		que.pop();
		for (int i = 0; i < 4; ++i) {
			const int ny = atop.y + dy[i];
			const int nx = atop.x + dx[i];
			int atime = atop.time;
			if (ny < 0 || ny > H || nx < 0 || nx > W) {
				continue;
			}
			if (i % 2) {
				if (i == 1) {

					atime+=hedges[atop.y+1][atop.x];
				}
				else {
					atime += hedges[atop.y][atop.x];

				}
			}
			else {
				if (i == 0) {

					atime += wedges[atop.y][atop.x];
				}
				else {
					atime += wedges[atop.y][atop.x+1];

				}
			}
			if (atime < mintime[ny][nx]) {
				mintime[ny][nx] = atime;
				que.push(aa{ ny,nx,atime });
			}
		}
	}
	int ans = mintime[gy][gx];
	cout << ans << endl;
*/


	//int N; cin >> N;
	//vector<long long int>nums;
	//for (int i = 0; i < N; ++i) {
	//	long long int a; cin >> a;
	//	nums.emplace_back(a);
	//}
	//sort(nums.begin(), nums.end());
	//reverse(nums.begin(), nums.end());
	//long long int ans = nums[0];
	//vector<long long int >rests (1, nums[0]);
	//for (int n = 1; n<N; ++n) {
	//	long long int now = nums[n];
	//	for (int j = 0; j < rests.size(); ++j) {
	//		if (now&&rests[j]) {
	//			now--;
	//			rests[j]--;
	//		}
	//	}
	//	ans += now;
	//	if (now > 0) {
	//		rests.push_back(now);
	//	}
	//	sort(rests.begin(), rests.end());
	//	reverse(rests.begin(), rests.end());
	//}
	//cout << ans << endl;
//


	int N; cin >> N;
	for (int i = 0; i < N; ++i) {
		nodes.push_back(Node(i));
	}
	for (int i = 0; i < N - 1; ++i) {
		int a, b; cin >> a >> b;
		nodes[a].chid.push_back(b);
		nodes[b].paid = a;
	}
	int a = 0;
	for (int i = 0; i < N; ++i) {
		if (nodes[i].paid==-1) {
			a = i;
		}
	}
	map<int, Mod>ans(getans(a));
	Mod aa = 0;
	for (auto i : ans) {
		aa += i.second;
	}
	cout << aa << endl;
	return 0;
}