Cho một cây có ~n~ đỉnh. Có bao nhiêu cách để đặt ~n~ số khác nhau ~1, 2, \dots, n~ vào cây, mỗi số trên một nút thỏa mãn rằng nút nhỏ hơn số của tất cả các nút là con của nó. Gốc của cây luôn là nút 1.

Do kết quả có thể rất lớn nên chỉ cần tìm số dư khi chia kết quả tìm được với ~666013~.

Yêu cầu: Tính số cách đặt các số vào cây thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên ghi số ~n~ (~1 \le n \le 100000~).
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~x~ và ~y~, thể hiện có một cạnh nối giữa hai đỉnh ~x~ và ~y~ (~x \neq y, 1 \le x, y \le n~).

Output

• In ra một số nguyên duy nhất là kết quả cần tìm.

Sample Input 1

5
1 2
3 1
2 4
2 5

Sample Output 1

8