|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
While eating one of his delicious mini-pharaohs, Prof. Farnsworth started wondering about their culture and how they ended up having a city with a system of directed roads in such a way that all points of interest can be reached from the main Pyramid, and there were only a few roads. In fact, it is known that at the end of their civilization, there were $N$ points of interest (including the main Pyramid) and exactly $N - 1$ directed roads.
It is also known that the final configuration of the roads was obtained by destroying some (maybe none) of the original roads and that at the beginning there were no cycles (not even self-loops) formed by the roads.
But the most interesting fact of all is that the final configuration of the city forms something that they call a Dominator Tree of the original. For some reason, they thought it would help to optimize some tasks.
In a Dominator Tree of a city,
- A point of interest $A$ dominates a point of interest $B$ if every path from the main Pyramid to $B$ must pass through $A$, and
- $A$ is said to immediately dominate $B$ if $A$ is the unique point of interest that strictly dominates $B$ but does not strictly dominate any other point of interest that strictly dominates $B$. Every point of interest, except the main Pyramid, has an immediate dominator. Every point of interest immediately dominates at most $12$ other points (and this is really important for security reasons).
Building a road from $A$ to $B$ if and only if $A$ immediately dominates $B$, we end up with the Dominator Tree of the city. Knowing all this, Prof. Farnsworth wants you to tell him how many distinct origins the city could have had.
Input
A line containing $N$ ($1 \leq N \leq 25$), the number of points of interest, the id of the main Pyramid is $1$.
Then follow $N-1$ lines, describing the final configuration of the city. Each line contains two integers, $A$ and $B$ $(1 \le A, B \le N)$, indicating that there is a directed road from point of interest $A$ to $B$.
Output
One line with a number, which is the remainder of dividing the number of distinct origins the city could have had by $83921$.
Sample test(s)
Input
4
1 2
1 3
3 4
Output
5
Input
4
1 2
1 3
1 4
Output
25
Input
6
1 2
1 3
1 4
1 5
1 6
Output
29281