Counting Original Chains in a DAG after Vertex Removal

Given a directed acyclic graph (DAG) with ( n ) vertices and ( m ) edges (not necessarily connected), we define a chain as a path ( w_0 \to w_1 \to \cdots \to w_p ) satisfying that ( w_0 ) has in-degree 0 and ( w_p ) has out-degree 0 in the original graph. Two chains are considered different if they have different lengths or different sets of vertices.

You are given ( q ) independent queries. In each query, you are given an integer ( k ) and ( k ) distinct vertices ( c_i ) to remove from the graph. Only chains from the original graph that remain completely intact (i.e. none of the vertices in the chain are removed) should be counted. Note that if removal creates new chains in the induced subgraph, those do not count.

Output the number of remaining chains modulo (10^9+7).

For example, consider a graph with a single chain:
( 1 \to 2 \to 3 \to 4 ). It has exactly one chain. If vertex 2 is removed, the answer is 0.

inputFormat

The first line contains two integers ( n ) and ( m ).

The next ( m ) lines each contain two integers ( u ) and ( v ), indicating a directed edge from ( u ) to ( v ).

Then follows an integer ( q ), the number of queries.

Each of the next ( q ) lines begins with an integer ( k ) followed by ( k ) distinct integers ( c_i ) (the vertices to be removed).

It is guaranteed that the vertices are numbered from 1 to ( n ).

outputFormat

For each query, output a single integer — the number of remaining chains (i.e. the number of original source-to-sink paths that are completely intact) modulo (10^9+7). Each answer should be printed on its own line.

sample

4 3
1 2
2 3
3 4
3
0
1 2
1 3

1
0
0