ACRush is very famous in Supercoder. Supercoder is a professional company which arranges online algorithmic contests and rates peoples based on those contests. In Supercoder algorithm contest ranklist, ACRush is ranked third. Now a days he is doing some analysis on his rating history in Supercoder algorithm contest. In Supercoder, an algorithm contest is termed as a Single Round Tournament (SRT). After each SRT is finished, rating of a contestant is updated according to his/her relative performance. ACRush collected all these rating information, and using those he created a line chart. To make things more clear, let us consider the following table as his rating info. SRT Rating 320 3 306 1 401 3 325 4 393 5 380 2 From this table, we see that his first SRT was SRT#306, and rating after that SRT was 1, so he marked point (1, 1) as r1 in graph paper, his second SRT was SRT#320 and rating after that SRT was 3, so he marked (2, 3) as r2, then he add r1 with r2 by a straight line and so on. In general for his i-th SRT he marked point (i, rating after i-th SRT) by ri. After marking all the points he will add point ri with ri−1 by straight lines, for all 1 < i ≤ N, Where N is the total number of SRTs he played. For better idea look at figure 1: Fig 1: Line chart cosidering all SRTs Fig 2: Line chart ignoring SRT #380 After drawing line chart, he became very interested about the number of peaks. There are two kinds of peaks in a line chart, 1) Upper Peak and 2) Lower Peak. Upper Peak is that point in a line chart whose previous and next point has smaller y coordinates and lower peak is that points in a line chart whose previous and next point has greater y coordinates. For example total number of peak in figure 1 is 3. Two of them upper peak, which are (3, 4) and (5, 5), and one of them is lower peak which is (4, 2). ACRush observed that by ignoring SRT#380, his line chart will become like figure 2, in which number of peak is only 1. By observing this he became more curious. Now he wants to know, by
2/2 ignoring 0 or more SRTs how many distinct line charts having K peaks is possible. ACRush calls these line charts K-peak Line charts, in a K-peak line chart he doesn’t allow two consecutive points to have same y coordinate. Input Input will start with an integer T (T ≤ 12), which indicates the number of test cases. Each case starts with a line having two integers N (1 ≤ N ≤ 10000) and K (0 ≤ K ≤ 50). Each of the next N lines will contain two integers SRT (1 ≤ SRT ≤ 1000000000) and Rating (1 ≤ Rating ≤ 1000000000). All the SRT numbers will be distinct. Output For Each test case output a single Line ‘Case #: W’, here # will be replaced by case number and W will be replaced by the number of distinct K-peak line charts modulo 1000000. Sample Input 3 61 320 3 306 1 401 3 325 4 393 5 380 2 41 101 3 102 2 103 2 104 4 30 102 2 101 1 103 3 Sample Output Case 1: 20 Case 2: 1 Case 3: 8