描述

今晚夜市很热闹，原来是烧烤店老板在搞优惠活动。小黑板上随意写上 k 个数（1-9之间的不重复整数）后，老板说出一个和 c。大家把黑板上的数字（可以重复取数）排成数字串，使数字串的每个数字之和刚好等于c，看看符合要求的数字串一共有多少种（不同排序的数字串是两个）。答对的人可以半价买单。注意每个数字可以使用的次数不限，也可以不用其中某些数字。

输入

第一行包括一个整数k，代表黑板上数字的个数。

第二行包括k个1~9且不会重复的整数，代表黑板上的数字。

第三行包括一个整数q，代表游戏轮数。

接下来q行，每行包括一个整数，代表和c。

输出

每轮游戏结果输出一行，代表答案。因为答案可能很大，所以要对10007取模。

输入样例

1 3 3 5 7 2 6 10 输出样例 1 1 3 提示 样例说明：黑板上有3个数字，分别是3 5 7。玩2轮，第一轮 凑 6，只有 1 种凑法 3 3；第二轮 凑10 ，有3种凑法 3 7，7 3，5 5。

对于10%的数据，k=1

对于40%的数据，k<=2, c<=10

对于70%的数据，q<=10