# Practice on Toph

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

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

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]. 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.

The first line contains three integers **N** (1 ≤ N ≤ 10^{5}), **M** (0 ≤ M ≤ 2*10^{5}) and K. (1 ≤ K ≤ 20) 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, **B[i]** (3 ≤ B[i] ≤ 10^{7}). The i^{th} of them is the beauty of the i^{th} vertex.

Each of the next K lines describe each level. The i^{th} line start with an integer S_{i} which is the number of nodes in level i and is followed by S_{i} integers, the **id** (1 ≤ id ≤ N) of the vertex in that level.

Then M lines follows. Each containing two integers **u** and **v** (1 ≤ u, v ≤ N). Which means there is an edge between vertex u and v.

The next line contains an integer **Q** (1 ≤ Q ≤ 10^{5}) which represents the number of queries. Then Q lines follows each having a single integer u.

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.

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.

73% Solution Ratio

imranziadEarliest,

IstiaqueShubhoFastest, 0.3s

SilentGLightest, 8.4 MB

mpnri2Shortest, 1457B

Login to submit

Idea: We can solve this problem applying Euler’s theorem and dynamic programming. If we understand t...