Little M-supremacist Little D is in a great mood today and is preparing a Christmas gift for Little M.

He bought a Christmas tree, which is a tree with $n$ nodes, where node $i$ has a color $c_i$. Little D thinks it won't look good if there are too many nodes of the same color, so there will be at most $5$ nodes with the same color.

Little M is very happy to receive the gift, but she has recently become interested in counting problems, so she has some questions she wants Little D to solve. Each time, Little M is interested in three different colors $a, b, c$, and she wants to know how many distinct non-empty connected subgraphs of this Christmas tree satisfy the condition that the number of nodes with colors $a, b, c$ are $n_a, n_b, n_c$, respectively. Since the number can be very large, output the remainder modulo $10^9+7$.

Little D solved this problem easily, of course. Although you have been fed dog food, you also want to train your skills. Can you solve this problem?

Input

The first line contains two numbers $n$ and $Q$, representing the size of the tree and the number of queries. The second line contains $n$ numbers, where the $i$-th number represents $c_i$, the color of the $i$-th node. The next $n-1$ lines each contain two numbers $a$ and $b$, representing an edge between node $a$ and node $b$. The next $Q$ lines each contain $6$ numbers $a, n_a, b, n_b, c, n_c$, representing the query as described in the problem.

Output

For each query, output one line representing the answer.

Examples

Input 1

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

Output 1

3
1
2

Constraints

For each $1 \le i \le n$, $1 \le c_i \le n$.

For each query, we have: $0 \le n_a, n_b, n_c \le 5$, $1 \le a, b, c \le n$, and $a, b, c$ are distinct.

For $10\%$ of the queries, $n, Q \le 10$.

For another $10\%$ of the queries, $n \le 15, Q \le 50$.

For another $10\%$ of the queries, $n, Q \le 1000$.

For another $5\%$ of the queries, $n, Q \le 50000$, and the input tree, if rooted at node $1$, has a maximum depth not exceeding $35$ (the depth of node $1$ is $0$).

For another $5\%$ of the queries, $n, Q \le 100000$, and the input tree, if rooted at node $1$, has a maximum depth not exceeding $35$ (the depth of node $1$ is $0$).

For another $20\%$ of the queries, $n, Q \le 100000$, and it is guaranteed that the sum of $(n_a + 1)^2 \cdot (n_b + 1)^2 \cdot (n_c + 1)^2$ over all queries is less than or equal to $10^8$.

For another $40\%$ of the queries, $n, Q \le 100000$, and it is guaranteed that the sum of $(n_a + 1)(n_b + 1)(n_c + 1)$ over all queries is less than or equal to $8 \cdot 10^6$.