BZPRO
#5215. [Lydsy2017省队十连测]商店购物
内存限制：512 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
在 Byteland一共开着 n家商店，编号依次为 1到 n，其中编号为1到 m的商店有日消费量上限，第 i家商店的日消
费量上限为wi。Byteasar每次购物的过程是这样的：依次经过每家商店，然后购买非负整数价格的商品，并在结账
的时候在账本上写上在这家商店消费了多少钱。当然，他在这家商店也可以什么都不买，然后在账本上写上一个0
。这一天， Byteasar日常完成了一次购物，但是他不慎遗失了他的账本。他只记得自己这一天一共消费了多少钱
，请写一个程序，帮助 Byteasar计算有多少种可能的账单。
输入格式
第一行包含三个正整数
n, m, k，分别表示商店的个数、有限制的商店个数以及总消费量。
第二行包含 m个整数，依次表示 w1;w2...wm。
1 ≤ m ≤ n，0≤ wi ≤ 300，1 ≤ n, k ≤ 5000000
m<=300
输出格式
输出一行一个整数，即可能的账单数，由于答案可能很大，请对1000000007取模输出。
样例
样例输入
3 2 8
2 1
样例输出
6
HINT
6 种方案分别为：{0; 0; 8}; {1; 0; 7}; {2; 0; 6}; {0; 1; 7};
{1; 1; 6}; {2; 1; 5}。
数据范围与提示
BZPRO