A	Game of Blocks
	Input	Standard Input
	Output	Standard Output

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 (10¹⁰⁰) 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 x 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. ith integer 1 ≤ len_i ≤ 750 denotes length of i^th color. Next line is positive integer n ≤ 10¹⁵.

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	Sample Output
4 3 3 3 5 11 3 3 5 3 1111111111111 4 1 1 100 100 1000000 3 1 1 1 5	Case 1: 12 Case 2: 20634244 Case 3: 94126777 Case 4: 243

---

Problemsetter: Tanaeem M Moosa, Special Thanks: Md. Arifuzzaman Arif