周末,小凯补完了上次训练赛的最后一道题,打算去超市购物。
超市里共有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 。
1
2 3 4
1 2
2