All Tracks Algorithms Dynamic Programming Problem

Harry Potter and the Deathly Hallows
Tag(s):

Medium-Hard, Medium-Hard

Problem
Editorial
Analytics

Voldemort's army is marching towards Hogwarts. The army consists of N different types of Death Eaters. Luckily, Harry knows Q spells, each of which will exterminate exactly K Death Eaters from the army. He wants to know the number of ways in which he can select a group of exactly K Death Eaters (of various types) he wishes to exterminate using each spell. Two groups are considered different if count of atleast one type of Death Eater is different in both the groups. We can assume that Death Eaters of same type are similar in all aspects.

Input

First line contains N , the types of Death Eaters. Next line contains N numbers where ith number is the number of Death Eaters in the army of ith type. Next line contain Q, the number of spells. Next Q lines contain a number K, the number of Death Eaters it can exterminate.

Output

Print Q lines with a number each giving the number of ways to select a group of Death Eaters of various types to be exterminated. Print the number mod 10^9 +7.

Constraints

1 <= N <= 10^6

1 <= a[i] <= 1000

1 <= Q <= 1000

1 <= K <= 1000

Note

Print ans mod(10^9 + 7).

Use Fast I/O.

SAMPLE INPUT
2
5 6
2
9
10
SAMPLE OUTPUT
3
2
Explanation

In The Sample Test case, there are 2 queries. For the first query, the value of K is 9 and the answer is 3. The 3 different ways are:-

  1. 3,6
  2. 4,5
  3. 5,4

Similarly, for the second query, the value of K is 10 and the answer is 2. The 2 different ways are:-

  1. 5,5
  2. 4,6
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

NIT Surat

Challenge Name

Epiphany 6.2

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications