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 $N$ nodes and M edges. The nodes are numbered from $1$ to $N$. You are given $Q$ queries.

Query: Given $K$ colors, the colors are numbered fron $1$ to $K$, 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 $1$ to $K$.
  2. No adjacent nodes have the same color.

Input

First line contains $N$ ($1 \le N \le 5 \times 10^5$), number of nodes and $M$ ($0 \le M < N$), number of edges.

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

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

Next $Q$ lines contain an integer $K$ ($1 \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 $10^9+7$.

Sample

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

Discussion

Statistics


79% Solution Ratio

EgorKulikovEarliest, 1M ago

salman.exeFastest, 0.0s

theunownLightest, 131 kB

theunownShortest, 630B

Submit

Login to submit