Color The Graph

Limits 2s, 512 MB

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

Query: Given KK colors, the colors are numbered fron 1 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 1 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 MM 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