# Color The Graph

Replay of BSMRSTU Home Qu...
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