You are given an acyclic, bidirectional graph with
$N$ nodes and M edges. The nodes are numbered from
$N$. You are given
$K$ colors, the colors are numbered fron
$K$, you have to find the number of ways for coloring the graph by maintaining the following rules.
First line contains
$1 \le N \le 5 \times 10^5$), number of nodes and
$0 \le M < N$), number of edges.
Next M lines contain two different integers
$1 \le U, V \le N$), an edge between
Next line contains
$1 \le Q \le 100$), number of queries.
$Q$ lines contain an integer
$1 \le K \le 10^9$), number of colors.
For each query, print the number of ways for coloring the graph. You have to print the mod value with
3 2 1 2 1 3 2 2 3