Subset of Sequences

ridowan007 SUST Intra University Pro...
Limits 1s, 512 MB

You will be given a set of sequences. Each sequence is a list of numbers.

Two sequences are K-similar if the first K or more numbers from the both sequences are same and appear in same order in both sequences (K must be less than or equal to the size of the smaller sequence). That is the K length prefix of both sequence is same. E.g. [1, 3, 5, 7, 9, 11] and [1, 3, 5, 7, 8, 11] sequences can be said 4-similar, 3-similar, 2-similar, 1-similar or 0-similar; [2, 4] and [2, 4, 6] are 2-similar, 1-similar or 0-similar; and [1, 2] and [2, 1] are only 0-similar.

Now you will be given Q values of K. For each given K, you have to tell how many ways we can take a non empty subset from the set of sequences so that any two sequence from the subset are K-similar. A subset of set A is a set that is contained in set A: all elements of the subset are also elements of set A regardless of order.

Input

The first line of the input is an integer N (2 ≤ N ≤ 10000), the number of sequences in this case.

For each of the next N lines, the first number of line i is Mi (1 ≤ Mi ≤ 1000000) which is the number of members in this sequence. Then there will be Mi integers, each j of those integers Wij (1 ≤ Wij ≤ 109) is jth element of ith sequence. Number of elements from all the sequences (sum of all Mi) is less than or equal to 106.

In next line, there will an integer Q (Q ≤ 100000), the number of queries.

The next line will have Q integers, each will be a different value of K (0 ≤ K ≤ 1000000).

Output

For each K in Q queries, print "Case I: R" where I is the query number and R is how many ways we can take a non empty subset from the set of sequences so that any two sequence from the subset are K-similar.

As the results can be very large, output its modulo by 1000000007.

Sample

InputOutput
4
5 1 3 5 7 9
5 1 3 5 7 11
2 2 4
3 2 4 6
5
5 4 3 2 1
Case 1: 2
Case 2: 3
Case 3: 4
Case 4: 6
Case 5: 6

In the sample, when K is 3, the subsets are {1st sequence}, {2nd sequence}, {4th sequence}, {1st and 2nd sequence}. So the result is 4.

Submit

Login to submit.

Statistics

72% Solution Ratio
iutictf8.23$moJxCEarliest, Nov '16
tuhin107494Fastest, 0.1s
iutictf8.24$1uA4SLightest, 32 MB
Tarik.amtolyShortest, 1089B
Toph uses cookies. By continuing you agree to our Cookie Policy.