Little Elephant and Sheet

All submissions for this problem are available.
The Little Elephant from the Zoo of Lviv wants to paint the sheet of paper. The sheet has the size 1 × Z and consists of Z consecutive cells numbered from 1 to Z inclusive (we use letter Z because N will denote another value below and the words "size" and "zoo" both contain letter 'Z' :))
There are also C available colors numbered from 1 to C inclusive. Current color of the ith cell is Col[i] (1 ≤ Col[i] ≤ C).
The Little Elephant can repaint some cells of the sheet. In a single move he chooses arbitrary pair of integers L and R such that 1 ≤ L ≤ R ≤ Z and some color Ci from 1 to C inclusive, after that he repaints all the cells on the segment [L, R] to the color Ci, that is, he assigns Col[j] = Ci for j from L to R inclusive. IMPORTANT: it is allowed to repaint each cell at most once during the whole sequence of moves.
Help the Little Elephant to find the total number of different sheets he can get in no more than K moves. Since the answer can be large, print it modulo 1000000007 (10^{9} + 7).
Two sheets are considered different if there exists at least one index i from 1 to Z inclusive, such that that A[i] is not equal to B[i], where A[i] is the color of the ith cell of the first sheet and B[i] is the color of the ith cell of the second sheet.
Little Elephant, in fact, has some enormous sheet of paper, possibly having billions of cells. But it has very specific structure. Namely, it consists of several blocks of consecutive cells, where all cells in each particular block have the same color (possibly different for different blocks), and the number of these blocks is relatively small. Consider the following example. Let our sheet of paper be {1, 1, 1, 2, 4, 4, 4, 1, 1} (numbers represent colors of the cells). Then it consists of 4 blocks, where the first block has 3 cells of color 1, the second block has 1 cell of color 2, the third block has 3 cells of color 4 and the last fourth block has 2 cells of color 1. It seems natural for consecutive blocks to be of different color but we allow opposite situation in the input too. So please DO NOT assume that two consecutive blocks in the input are always of different color.
Input
The first line of the input contains a single integer T, the number of test cases. Then T test cases follow. The first line of each test case contains three space separated integers N, C and K. Here N is the number of blocks in the sheet, C is the number of available colors and K is the upper bound on the number of moves Little Elephant can make. Each of following N lines contains two space separated integers S[i] and M[i], where S[i] is the color of the ith block and M[i] is the number of cells in the ith block. So the above value Z equals to M[1] + M[2] + ... + M[N].
Output
For each test case output a single line containing the number of different sheets the Little Elephant can get using at most K moves. As was mentioned above you should output this number modulo 10^{9} + 7.
Constraints
1 ≤ T ≤ 7
1 ≤ N ≤ 7
1 ≤ C ≤ 10^{9}
1 ≤ K ≤ 7
1 ≤ S[i] ≤ C
1 ≤ M[i] ≤ 10^{9}
Example
Input: 3 1 47 1 1 1 2 2 1 1 1 2 1 2 3 2 1 2 2 2 Output: 47 3 57
Explanation
Case 1. Here the sheet consists of one cell of color 1. We have 47 available colors. Using one move we can color this cell in any of available colors. So we can get 47 different sheets.
Case 2. Here the sheet of paper is {1, 2} (numbers represent colors of the cells). We have 2 available colors. So there exist 4 different sheets of 2 cells. Using at most one move we can achieve every such sheet except {2, 1}. Indeed,
 Sheet {1, 1} is achieved by repainting the second cell at color 1.
 Sheet {1, 2} is achieved using no repainting.
 Sheet {2, 2} is achieved by repainting the first cell at color 2.
To get {2, 1} we need at least two moves. So the answer is 3.
Author:  witua 
Tags  cook28, dynamicprogramming, hard, matrixexpo, witua 
Date Added:  23072012 
Time Limit:  7 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions