RoAlgo Contest #11 - Back to School 2024 | Crucks

Task

We have a tree with $N$ nodes, where each node contains a natural number, and the values found in the nodes form a permutation of the set $\{1, 2, \dots, N\}$.

This tree has its root at node $1$ and is special in that each node has at most $4$ children.

The following process is defined:

• A sequence is initialized as empty.
• A pawn is placed on node $1$, which is marked as visited. The value of node $1$ is added to the sequence.
• As long as there are unvisited nodes, the pawn moves to a neighboring node of its current position, even if that node has already been visited.
• If the node the pawn arrives at has not been visited, it is marked as visited and the node's value is added to the sequence.
• The pawn can only move to an already visited node if all nodes in the subtree of the current node have been visited.

It is observed that after this process, the resulting sequence will be a permutation. How many processes will result in a permutation with an odd number of inversions?

Two processes are considered different if the resulting sequence is different. The answer should be calculated modulo $10^9+7$.

Input data

The first line contains $N$, the number of nodes in the tree. The second line contains $N$ values, representing the values of the nodes. The next $N-1$ lines contain two values each, representing the endpoints of the tree's edges.

Output data

On the first line, print the number of resulting sequences, modulo $10^9+7$.

Constraints and clarifications

• $1 \leq N \leq 10^3$
• Each node has at most $4$ children.
• The answer is printed modulo $10^9+7$.
• For tests worth $15$ points, $N \leq 18$.
• For tests worth $10$ more points, $N \leq 100$.
• For tests worth $10$ more points, each node has at most $2$ children.
• For tests worth $25$ more points, each node has at most $3$ children.

Example 1

stdin

5
3 1 4 2 5
1 2
1 3
3 4
3 5

stdout

2

Explanation

The following sequences can be obtained from the processes:

• $\{3, 1, 4, 2, 5\}$ — $3$ inversions
• $\{3, 1, 4, 5, 2\}$ — $4$ inversions
• $\{3, 4, 2, 5, 1\}$ — $6$ inversions
• $\{3, 4, 5, 2, 1\}$ — $7$ inversions

Note that the sequence $\{3, 4, 5, 1, 2\}$ is not valid.
The pawn would have the following path: $1 \rightarrow 3 \rightarrow 5 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$.
The pawn is not allowed to move from node $3$ to node $1$ because there are still unvisited nodes in the subtree of node $3$.

Example 2

stdin

17
8 12 4 7 3 5 1 17 11 2 6 9 10 14 16 15 13
1 2
1 3
1 4
2 8
2 9
2 10
2 11
4 5
4 6
6 7
10 12
10 13
13 14
13 15
13 16
13 17

stdout

6912