3140. 凑数

种钱币,面值为 ,每一种钱币数量不限。

询问用这些钱币组成 元有几种方法。


输入

第一行输入一个整数 ,表示钱币面值种数。

第二行输入 个不同的整数 ,表示每种钱币面值,保证

第三行输入一个整数 ,表示需要组成的钱数。


输出

输出一个整数,表示方案数。(结果可能会很大,你需要将结果模上1000000007)


样例

输入1

 2
 1 10
 11

输出1

 2

输入2

3
1 2 3
1

输出2

1


说明

第一组样例中, ,故有两种。

第二组样例中,组成 的方式只有一种。


难度等级: 0
总通过次数: 8
总提交次数: 65