RoAlgo Contest #11 - Back to School 2024 | Crucks

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 64MB Input: Output:

Task

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

This tree has its root at node 11 and is special in that each node has at most 44 children.

The following process is defined:

  • A sequence is initialized as empty.
  • A pawn is placed on node 11, which is marked as visited. The value of node 11 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 109+710^9+7.

Input data

The first line contains NN, the number of nodes in the tree. The second line contains NN values, representing the values of the nodes. The next N1N-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 109+710^9+7.

Constraints and clarifications

  • 1N1031 \leq N \leq 10^3
  • Each node has at most 44 children.
  • The answer is printed modulo 109+710^9+7.
  • For tests worth 1515 points, N18N \leq 18.
  • For tests worth 1010 more points, N100N \leq 100.
  • For tests worth 1010 more points, each node has at most 22 children.
  • For tests worth 2525 more points, each node has at most 33 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, 1, 4, 2, 5\}33 inversions
  • {3,1,4,5,2}\{3, 1, 4, 5, 2\}44 inversions
  • {3,4,2,5,1}\{3, 4, 2, 5, 1\}66 inversions
  • {3,4,5,2,1}\{3, 4, 5, 2, 1\}77 inversions

Note that the sequence {3,4,5,1,2}\{3, 4, 5, 1, 2\} is not valid.
The pawn would have the following path: 1353121341 \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 33 to node 11 because there are still unvisited nodes in the subtree of node 33.

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

Log in or sign up to be able to send submissions!