You are given a tree A of n nodes.There are m queries.In each query,you are given a tree B of m nodes and you have to answer how many connected subgraphs of A is isomorphic to B.Because the answer may be too large,you only need to output it modulo .

输入描述:

The first line contains an integer n.

The next n-1 lines,each line contains two integers - the endpoints of an edge of A.

The next line, an integer t - the number of queries.

For each query:

The first line contains an integer m.

For each of the next m-1 lines, each line contains two integer - the endpoints of an edge of B.

输出描述:

For each query, output a line containing one integer that stands for the answer.

4
1 2
1 3
1 4
1
2
1 2

3

备注:

For all test datas, , , .