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.
Every node is colored with exactly one color from 1 to K.
No adjacent nodes have the same color.
Input
First line contains N (1≤N≤5×105), number of nodes and M (0≤M<N), number of edges.
Next M lines contain two different integers U and V (1≤U,V≤N), an edge between U and V.
Next line contains Q (1≤Q≤100), number of queries.
Next Q lines contain an integer K (1≤K≤109), 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+7.