순위 매기기

이쿠타가 사는 마을에는 $N$개의 탑이 있다. 각 탑에는 0부터 $N-1$까지의 서로 다른 번호가 붙어 있으며, 번호 $i$인 탑을 탑 $i$라고 부른다. 호기심 많은 이쿠타는 $N$개 탑의 높이에 흥미를 느껴 그 대소 관계를 나타내는 표 $T$를 만들기로 했다. $T$는 $N \times N$개의 원소를 가지며, 각 원소 $T_{i, j} (0 \leq i, j \leq N - 1)$는 다음과 같이 정의된다.

• $T_{i, j} = -1 \iff$ 탑 $i$의 높이가 탑 $j$의 높이보다 작다

• $T_{i, j} = 0 \iff$ 탑 $i$의 높이와 탑 $j$의 높이가 같다

• $T_{i, j} = 1 \iff$ 탑 $i$의 높이가 탑 $j$의 높이보다 크다

이쿠타는 표 $T$를 만들기 위한 조사로 두 탑을 골라 높이를 비교하는 일을 $N-1$번 반복했다.

이쿠타의 조사에 관해 다음이 알려져 있다.

• $i$번째 비교 $(1 \leq i \leq N - 1)$에서 탑 $a_{i}$와 탑 $b_{i}$를 골랐다면 탑 $a_{i}$의 높이가 탑 $b_{i}$의 높이보다 컸다. 즉 $T_{a_{i}, b_{i}} = 1$, $T_{b_{i}, a_{i}} = -1$이었다.

• 각 탑은 자기 자신보다 큰 탑과 많아야 한 번만 비교되었다.

아쉽게도 이쿠타의 조사 정보만으로 표 $T$의 내용을 유일하게 결정할 수 있는 것은 아니다. 표 $T$가 이쿠타의 조사와 모순되지 않고, $T$가 정의되는 탑 높이 조합이 존재할 때 $T$를 올바른 표라고 하자. 올바른 표로 가능한 것이 몇 가지인지 계산해 이쿠타에게 알려 주자.

단, 비교된 두 탑의 높이는 서로 다르지만 모든 탑의 높이가 서로 다르다고는 할 수 없다.

입력은 다음 형식으로 주어진다.

$N$

$a_{1}$ $b_{1}$

...

$a_{N-1}$ $b_{N-1}$

$N$은 탑의 수를 나타낸다. $a_{i}$, $b_{i}$ ($1 \leq i \leq N - 1$)는 탑 $a_{i}$가 탑 $b_{i}$보다 높다는 것을 나타낸다.

가능한 올바른 표 $T$의 개수를 1,000,000,007로 나눈 나머지를 출력하라.

입력의 각 변수는 다음 조건을 만족한다.

• $1 \leq N \leq 200$

• $0 \leq a_{i}, b_{i} < N$

• $a_{i} \neq b_{i}$

• 서로 다른 탑이 같은 높이일 수도 있다.

• 이쿠타의 조사 결과 자체는 모순이 없으며, 적어도 하나의 조사 결과와 모순되지 않는 표 $T$가 존재한다.