问题 A: 小凯逛超市

内存限制:256 MB 时间限制:3 S
题面:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

周末,小凯补完了上次训练赛的最后一道题,打算去超市购物。
超市里共有n种物品,每种物品的价格为 gi ,体积为 1。每个物品可以购买无限次,求在总花费不超过 V 的前提下,恰好填满大小为 m 的背包的方案数。由于答案可能过大,请将答案对 1e9+7 取模后输出。


输入格式

第一行一个正整数 T ,表示有 T 组数据。
对于每组数据:
第一行三个正整数 n,m,V,如题意所描述。第二行包含 n 个整数 g 1,g 2,⋯,g n ,每个数都被单个空格隔开。对于 100% 的数据,保证 1≤T≤5,1≤n,m,V,g i≤400 。


输出格式

共T行,对于每组数据,输出一个ans, 表示方案数取模之后的值。

输入样例 复制

1
2 3 4
1 2

输出样例 复制

2