NPC2016E - Quest Hunter

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 Xi 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 109 + 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, Xi, 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 

Explanation

  • For the first case, total amount of money is (1+2+3) = 6 and there are 3 weapons. Quest Hunter can sell it using these configurations (1,1,4), (1,2,3), (2,2,2)
  • For second case, Quest Hunter can't buy any weapons

Constraints:

  • 1 ≤ T ≤ 102
  • 1 ≤ N,Y,Xi ≤ 103

Added by:Louis Arianto
Date:2017-01-08
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:NPC Schematics 2016

hide comments
2018-05-22 07:22:56
I found the problem statement ambiguous; clarification: 1) They want to maximize the number of weapons they buy. Lets call that M. 2) They will use the least amount of money possible to buy M weapons. Lets call that amount V. 3) They want to know how many unordered ways there are to assign V gold to M weapons so that each costs at least 1.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.