# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Christmas Tree

Professor Rio has an amazing Christmas tree. Unlike other trees, this Christmas tree has some special properties.

All the vertices are categorized in different levels (Level

**1**, Level**2**, … , Level**K**).There may exist an edge between vertex

**u**and**v**only if their levels are adjacent to each other. The vertex with the higher level number will be the parent of another vertex.There are at most

**20**levels in the Christmas tree.Each of the vertices of the tree has two types of special values,

**beauty**and**attractiveness**.All the beauty values are

**prime**numbers.Professor Rio doesn’t like some of the prime numbers and so he has restricted them.

**The restricted list is [2,3,5,11,13,41,148721]**. So the beauty values also will not be from this restricted list.

Initially, you are given the beauty of all of the vertices. But you will have to find out the attractiveness of some of them. There is a formula to calculate this attractiveness value.

If a vertex **u** has **X** children **v1, v2, v3, … , vX**, then the attractiveness of **u** is **B[u]^A[v1] + B[u]^A[v2] + B[u]^A[v3] + … + B[u]^A[vX]**.

But if a vertex **u** has no child then the attractiveness of **u** is **B[u]**.

Here, **A[i]** = attractiveness of vertex **i** and **B[i]** = beauty of vertex **i**.

#### Input

The first line contains three integers **N**, **M** and **K**. Here, **N** is the number of nodes in the tree, **M** is the number of edges and **K** is the number of levels.

The next line contains **N** integers, **i ^{th}** of them is the beauty of the

**i**vertex.

^{th}Each of the next **K** lines describe each level. The **i ^{th}** line start with an integer

**S**which is the number of nodes in level

_{i}**i**and is followed by

**S**integers, the id of the vertex in that level.

_{i}Then **M** lines follows. Each containing two integers **u** and **v**. Which means there is an edge between vertex **u** and **v**.

The next line contains an integer **Q** which represents the number of queries. Then **Q** lines follows each having a single integer **u**.

**Constraints:**

**1 ≤ N,Q ≤ 10 ^{5}**

**0 ≤ M ≤ 2*10**

^{5}**1 ≤ id,u,v ≤ N**

**3 ≤ B[i] ≤ 10**

^{7}**1 ≤ K ≤ 20**

#### Output

For each of the query, you have to print the attractiveness of vertex **u**. As this value might become huge, print it with modulo **1000000007**.

#### Samples

Input | Output |
---|---|

7 8 3 7 7 7 7 17 7 19 1 1 2 2 3 4 4 5 6 7 1 2 1 3 2 4 2 5 2 7 3 4 3 6 3 7 7 1 2 3 4 5 6 7 | 632804163 618763218 107227964 7 17 7 19 |

Explanation of the sample test case:

A[4] = B[4] = 7

A[5] = B[5] = 17

A[6] = B[6] = 7

A[7] = B[7] = 19

A[2] = (7^{7} + 7^{17} + 7^{19}) % (10^{9}+7) = 618763218

A[3] = (7^{7} + 7^{7} + 7^{19}) % (10^{9}+7) = 107227964

A[1] = (7^{(77 + 717 + 719)} + 7^{(77 + 77 + 719)}) % (10^{9}+7) = 632804163

Note: Christmas tree of professor Rio is not a normal tree. So the total number of edges doesn’t depend on the total number of vertex.

#### flash_7

Tarango works NSUPS. He loves to play FIFA & travel with friends. When not solving problems, he spends most of his time day dreaming. And, he most definitely is not a "manga lover". →