All submissions for this problem are available.
Sam visits the most famous sweet shop in his city. The shop has an assortment of sweets of different variety. It contains a1 sweets of 1st kind, a2 sweets of 2nd kind, and so on, upto N.
Now Sam has been restricted by his mother, to select exactly S number of sweets from the shop to eat. You have to help him find out the number of ways in which he can select S sweets. Sam may have multiple queries for you and you are expected to answer them all.
First line contains integer N, such that there are N different kinds of sweets.
The following N lines represent the amount of sweets of each kind, i.e., the integer on i-th line represents the number of sweets of i-th kind.
Next line contains an integer Q, the number of queries to follow.
The following Q lines contain an integer S each, such that you have to report the number of ways in which S sweets can be selected modulo (10^9 + 7).
The output consists of Q lines, such that each line consists of the output of the corresponding query, i.e., the number of ways in which S sweets can be selected.
- N ≤ 106
- 1 ≤ Amount of sweets of each kind ≤ 103
- 1 ≤ Q ≤ 104
- 1 ≤ S ≤ 2000
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions