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.
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).
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.
| Input | Output |
|---|---|
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.