Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Subset of Sequences

By ridowan007 · 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.

Discussion

Statistics


70% Solution Ratio

NJRafiEarliest, Dec '16

dip_BRURFastest, 0.2s

oneoff.0SS46wYaVfLightest, 32 MB

Tarik.amtolyShortest, 1089B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.