John decided to buy his son Johnny some mathematical toys. One of his most favorite toy is blocks of different colors. John has decided to buy blocks of C different colors. For each color he will buy googol (10100) blocks. All blocks of same color are of same length. But blocks of different color may vary in length. Jhonny has decided to use these blocks to make a large 1 × n block. He wonders how many ways he can do this. Two ways are considered different if there is a position where the color differs. The example shows a red block of size 5, blue block of size 3 and green block of size 3. It shows there are 12 ways of making a large block of length 11. Input Input starts with a positive integer T ≤ 25. T test cases follow. Each test case starts with an integer 1 ≤ C ≤ 100. Next line consists c integers. i-th integer 1 ≤ leni ≤ 750 denotes length of i-th color. Next line is positive integer n ≤ 1015. Output For each case output case number followed by the number of ways Johnny can make the desired block modulo 100000007 (a prime number). See sample output for exact format. Sample Input 4 3 335 11 3 353 1111111111111 4 1 1 100 100 1000000 3 111 5
2/2 Sample Output Case 1: 12 Case 2: 20634244 Case 3: 94126777 Case 4: 243