Mr. Foring and n-dimensions

The great Grasshopper “Foring” recently learned from the story “The ant and a grasshopper” that he should be planning for future things. Learning this, He devoted in collecting food for His family. But life isn’t so easy for Mr. Foring. As He has a very big family. To collect food for all of them most the time he needs to visit another universe with different dimensions.

For simplicity we are going to describe universe as a maze. There can up to n dimensional universe, which can be K sized in each axis. Position of Mr. Foring at a certain moment can be determined with n parameters. For example, in a 3 dimensional universe Mr. Foring’s position can be determine by coordinate (p1, p2, p3). Where, pi describes his position in i-th axis in 3 dimensional universes. Mr. Foring can go positive as long as it is not greated than K. For example, from (p1, p2, p3) Mr. Foring has 3 different choices (p1+1, p2, p3), (p1, p2+1, p3) and (p1, p2, p3+1). Similarly, for n dimension there at ( p1, p2, p3 .. pn ) he has n different moves to go to n different coordinate which will be one of these:

Now, he is visiting a n-dimensional universe, where he wants to collect F food items, each at a different coordinate. Mr. Foring has to start with first item which is always at (1,1,1,…1) and finish with F-th item which is always at (K,K,K,…K). He has to collect all the other F-2 items in the given order.. As Mr.Foring doesn’t have too much time he decided to take the fastest route to collect all the food. But discovered that there are multiple ways to collect all food in the least amount of time. As Mr. Foring is not good at math he wants your help. Can you help ?

Input

The first line contains an integer T, which indicate the number of test cases to be processed. Each test case contains 3 integers N, K and F, respectively representing number of dimensions, size of the dimensions and number of Food items. Followed by, F-2 lines each containing N integers denoting the coordinate of the i+1-th food item.

Output

For each case print a single line in the “Case c: X”. Here c is the case number and X is the number of ways Mr.Foring can collect food. As X can be very large make the X mod 1000000007.

Sample

Input	Output
3 2 15 3 3 3 2 16 5 2 1 4 2 6 3 3 15 4 1 9 1 5 6 2	Case 1: 16224936 Case 2: 10296594 Case 3: 0