Alice owns a shop in elbonia, and she takes great pride in varying the way that she makes change for her customers. she gives them one coin at a time, and tries to give the customers a sequence of coins that she has never used before. it that in elbonia the denominations and names for the coins change every year.
input format the first line of input contains an integer n, 1 < = n < = 20, which indicates the number of coin denominations currently in use. the next line contains n positive integers, each less than 1000, which give the coin denomenations. note that each denomenation will be unique, and there will always be one denomenation equal to 1. the next line gives a value 9, 1 < = q< = 10 which provides the number of coin queries. the following qlines each contain a query in the form of an integer ci, 1 < = c; < = 10%. note: the denominations are not necessary unique. in other words, it is possible that elbonia is using two coins both equal to one. however, one would distinguish sequences based on the type of coin used, not the denomination.
output format for each query, you should output, on a line by itself, the number of distinct sequences of coins that alice can use to make change equal to c; since this number can be very large, you should output the result mod 10° + 7.