Given a tree with N vertices. How many ways are there to place N different numbers 1, 2, ..., N in the tree, each number on a node such that node A is less than the number of all nodes that are children of A. The root of the tree is always node 1.

Since the result can be very large, just find the remainder when dividing the result by 666013.

INPUT

• The first line contains the number N (1 ≤ N ≤ 10⁵)
• Next N - 1 lines, each line contains 2 integers x and y, representing an edge connecting two vertices x and y (x ≠ y, 1 ≤ x, y ≤ N)

OUTPUT

• Print a single integer that is the result to be found

Example

Sample input

5
1 2
3 1
2 4
2 5

Sample output

8

Scoring

• Subtask 1: 60% tests with N ≤ 2000
• Subtask 2: 40% tests with N ≤ 10⁵