Wstęp do programowania w C++

Dziś profesor Algobit będzie robił obiad. Poszedł więc do sklepu, zakupił produkty, między innymi także ziemniaki. Poprosił więc panią ekspedientkę o kilogram. Ona zapakowała mu w reklamówkę i zapytała czy 1,2 kg może być, na co profesor odpowiedział, że to jest za dużo. Pani odłożyła trzy ziemniaki i okazało się, że po zważeniu waga pokazała 980 g. Profesor stwierdził, że to jest za mało i chce dokładnie 1 kg. Pani Ania (tak miała na imię ekspedientka) nieco poirytowana stwierdziła, że nie da się dokładnie wyważyć 1 kg ziemniaków. Na to profesor popatrzył na ziemniaki i z uśmiechem na twarzy oznajmił, że da się to zrobić na dokładnie sześć sposobów.

Zakładamy, że dwa ziemniaki o tej samej wadze to dwa różne ziemniaki. Twoim zadaniem jest sprawdzenie, czy profesor ma rację.

Wejście

W pierwszym wierszu n określająca liczbę ziemniaków, jakie bierzemy pod uwagę (liczba ta jest nie większa niż 1000).

W drugim wierszu n liczb całkowitych, określających wagi kolejnych ziemniaków (0 < n < 501).

Następnie jedna liczba q, określająca liczbę zapytań (q < 10 000).

Każde zapytanie jest wagą o wartości k, jaką profesor chce uzyskać nakładając ziemniaki (0 < k < 2 000 001). 

Wyjście

Dla każdego zapytania liczba sposobów uzyskania żądanej przez profesora wagi modulo 10⁹ + 9.

Przykład

Wejście:
5
100 100 200 100 200
3
200
400
300

Wyjście:
5
7
7

Wyjaśnienie
Dla rozróżnienia ziemniaków ponumerujmy kolejne wagi: 1001, 1002, 2001, 1003, 2002
Liczbę 200 możemy przedstawić jako: {1001+1002}, {1001+1003}, {1002+1003}, {2001}, {2002}.
Liczbę 400 możemy przedstawić jako: {1001+1002+2001}, {1001+1003+2001}, {1002+1003+2001}, {1001+1002+2002}, 
{1001+1003+2002}, {1002+1003+2002}, {2001+2002}