Heaps of Fun

노드가 n개인 루트 있는 트리가 있고, 각 노드에는 1부터 n까지 번호가 붙어 있다. 각 노드에는 고정된 정수 b가 주어지며, 노드마다 구간 [0..b]에서 균등하게 임의의 실수를 하나 고른다.

이렇게 고른 임의의 값들이 트리를 힙으로 만드는 확률을 구하라. 즉, 각 노드의 임의의 값이 자식 노드의 임의의 값보다 작아야 한다.

이 확률은 항상 유리수 P/Q로 나타낼 수 있고, Q ≠ 0 (mod 10^9+7)이다. 확률을 P·Q^−1 mod 10^9+7의 형태로 출력하라. 여기서 Q^−1은 Q의 모듈로 10^9+7 곱셈 역원인 정수이다 (Q·Q^−1 ≡ 1 (mod 10^9+7)). (참고: P·Q^−1 mod 10^9+7은 P와 Q가 서로소인지와 무관하고 오직 비 P/Q에만 달려 있다.)

각 테스트 케이스는 트리의 노드 수를 나타내는 정수 n (1 ≤ n ≤ 300)이 있는 한 줄로 시작한다.

다음 n개 줄에는 각각 트리의 한 노드를 나타내는 공백으로 구분된 정수 b (1 ≤ b ≤ 10^9)와 p (0 ≤ p ≤ n)가 주어진다. b는 노드에 고정된 정수 값이고, p는 부모 노드의 번호이다. 노드는 순서대로 나열되며, 노드 1이 처음이고 그다음 노드 2, 이런 식이다. 부모가 p=0인 노드는 하나뿐이며, 이것이 트리의 루트이다.

확률을 (P·Q^−1) mod (10^9+7)로 나타낸 정수 하나를 출력한다.