Practice on Toph

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

Color The Graph

By RamprosadG · Limits 2s, 512 MB

You are given an acyclic, bidirectional graph with NN nodes and M edges. The nodes are numbered from 11 to NN. You are given QQ queries.

Query: Given KK colors, the colors are numbered fron 11 to KK, you have to find the number of ways for coloring the graph by maintaining the following rules.

  1. Every node is colored with exactly one color from 11 to KK.
  2. No adjacent nodes have the same color.

Input

First line contains NN (1N5×1051 \le N \le 5 \times 10^5), number of nodes and MM (0M<N0 \le M < N), number of edges.

Next M lines contain two different integers UU and VV (1U,VN1 \le U, V \le N), an edge between UU and VV.

Next line contains QQ (1Q1001 \le Q \le 100), number of queries.

Next QQ lines contain an integer KK (1K1091 \le K \le 10^9), number of colors.

Output

For each query, print the number of ways for coloring the graph. You have to print the mod value with 109+710^9+7.

Sample

InputOutput
3 2
1 2
1 3
2
2
3
2
12

Discussion

Statistics


81% Solution Ratio

EgorKulikovEarliest, Jun '20

Deshi_TouristFastest, 0.0s

theunownLightest, 131 kB

Deshi_TouristShortest, 629B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.