You are given a rooted tree with the root at node 1. Each edge in the tree can either be a solid edge or a virtual edge. A valid chain decomposition is defined as one where each node has at most one solid edge leading to its children.

Next, we define the operation access(u) :

1. For each node on the chain from to the root, set all edges leading towards its children to virtual edges.
2. Set all edges on the chain from to the root to solid edges.

Initially, the entire tree consists of virtual edges. After operations, results from performing access() on , where is a permutation of integers from 1 to .

Now, you are given the status of each edge on . You want to determine how many permutations exist such that performing operations in order according to results in .

Additionally, there are modifications to . Initially, consists entirely of virtual edges. Each modification specifies a node , and performs the access(u) operation on . The modifications are not independent. After each modification, you need to output how many permutations satisfy the sequence of operations to eventually obtain . Answers should be given modulo .

The first line contains two positive integers .

The second line contains  integers , where  denotes the parent node of node .

The next  lines each contain a single integer , indicating an access(u) operation on .

There are  lines of output, each containing a single integer representing the answer after each modification.

8 9
1 2 1 2 5 5 2
6
2
6
8
3
1
1
5
8

5040
1680
5040
1680
1680
280
280
5040
1680

.