Occurrences Solution Codeforces Educational Round 144
A subarray of arrayfrom index to the index is the array . The number of occurrences of the array in the array is the number of subarrays of such that they are equal to .
You are given every given subarray , the number of occurrences of in the array is not less than the number of occurrences of each non-empty subarray of in . Note that if doesn’t occur in , and no subarray of occurs in , this condition is still met for .arrays ; the elements of these arrays are integers from to . You have to build an array consisting of integers from to in such a way that, for
Your task is to calculate the number of different arraysyou can build, and print it modulo .
The first line contains three integers, and ( ) — the number of the given arrays, the desired length of the array , and the upper bound on the values in the arrays.
Thenlines follow. The -th line represents the array . The first integer in the -th line is ( ) — the number of elements in ; then, integers from to follow — the elements of the array .
Additional constraint on the input:; i. e., the number of elements in the given arrays in total does not exceed .
Print one integer — the number of different arraysyou can build, taken modulo .
2 4 3 2 1 2 1 3
2 4 3 2 1 2 3 3 2 1
1 42 1337 2 13 31