Tatama Land is on a crisis. Recently, a dragon woke up and will destroy Tatama Land to ashes. Hearing this news, Pheo, Waca, and Wembo decided to create a guild called Quest Hunter to slay the dragon.

In order to defeat the dragon, they want to buy weapons first. They visit J0I Blacksmith, which sells N weapons, each with a price of X_i gold. As Quest Hunter only have Y golds, they want to buy as many weapons as they can using Y golds.

After buying weapons, they go to a local tavern to hire mercenaries for their guild. Each mercenary should buy a weapon they just bought. However, Quest Hunter lost the bill, and they totally forget how much gold for each weapon. They decided to randomly give a price to each weapon, but no weapon will costs 0 gold, and the total price of all weapons should be the same amount with total gold used to buy those weapons. Now, they're curious about how many price configurations available. As the answer can be very large, output it with modulo 10⁹ + 7

Input

An integer T, number of test cases in the first row
For each testcase:
- First row is an integer N
- Second row contains N integer, X_i, the price of each weapon
- Third row is an integer Y 

Output

For each testcase, output "Case #C: D" where C is the testcase number and D is the number of configurations.

Example

Input:
2
5
1 2 3 4 5
6
4
2 2 2 2
1

Output:
Case #1: 3
Case #2: 0