串联电阻问题

Time Limit: 6000 ms Memory Limit: 65536 KiB

Problem Description

一家电子商店计划购入若干盒电阻器,每盒至少有2500个阻值相同的电阻,不同盒子中的电阻阻值不同。他们计划购入4至20盒,其中一盒装着阻值为1kΩ的电阻,但他们尚未确定其他盒子中电阻的阻值。

如果你把电阻串联起来,所得新电阻的阻值等于原来各电阻阻值之和。例如,你串联(以任何顺序)3个500kΩ,2个200kΩ,1个50kΩ,2个20kΩ,1个5kΩ和2个2kΩ的电阻,就会得到阻值为1999kΩ的等效电阻。类似地,你可以用2个2kΩ和1个1kΩ的电阻或者5个1kΩ的电阻来代替原来那一个5kΩ的电阻而不改变总电阻的阻值。为了决定需要购买多少盒及每盒中电阻的阻值,商店想在已给出一种购买方案的情况下,计算出用串联的方法获得各种阻值电阻的容易程度。也就是说,给出盒子的数量b和各盒中电阻的阻值1=v1< v2< ...< vb,他们想知道对于若干个阻值n,分别有多少种串联方法可以获得阻值为n的电阻,单位为kΩ。

Input

输入数据包含若干方案。每个方案以一个整数b(1<=b<=20)开始。b等于0表示文件结束。方案的第2行是b个按递增顺序排列的整数,以1开始,按顺序分别代表v1到vb。接下来的若干行每行都有一个整数n,代表需要串联获得的电阻值,范围从1到1999,以0结束,这里的0不被处理。

Output

对输入数据的每个阻值n,输出串联获得nkΩ电阻的方法总数,每个数一行,且均为每一行的第1列开始输出。

Sample Input

9
1 2 5 10 20 50 100 200 500
1
5
10
42
50
137
500
1999
0
4
1 2 3 4
1
10
3
2
0
0

Sample Output

1
4
11
271
451
15154
6295435
27888185754
1
23
3
2

Hint

Source