During the season of autumn, leaves change colours and fall to the ground. To celebrate the autumn spirit, you are given a tree with nodes and different colours, where each node has a colour , and . For each colour from to , you must answer a query on the tree. The following process occurs: every second, a random leaf node is removed from the tree, falling to the ground. This process ends when colour is completely removed from the tree, or there is only node left. Out of every possible sequence of falling leaves, determine the number of sequences where colour is completely removed from the tree in the shortest amount of time. Note that if the colour does not exist, or the colour cannot be removed, there are sequences where it is removed.

#### Constraints

##### Subtask 1 [30%]

##### Subtask 2 [70%]

No additional constraints.

#### Input Specification

The first line contains space-separated integers and .

The next line contains space-separated integers, the th of which is .

The next lines contain space-separated integers and , denoting an edge between nodes and .

#### Output Specification

Output lines, where the -th line contains the number of sequences where colour is completely removed from the tree in the shortest amount of time. Since these numbers may be large, please output the answers modulo .

#### Sample Input

```
10 3
1 3 3 2 1 3 1 1 2 2
1 6
3 9
4 6
5 2
2 10
7 10
8 6
6 9
9 10
```

#### Sample Output

```
24
105
630
```

## Comments