U663710 疯狂的背包问题(6) - 完全背包问题（计数组合问题）

动态规划问题中的完全背包问题模板题，本题考察的是**方案计数**而非最优价值或可行性。

有 $N$ 种物品和一个容量是 $V$ 的背包。每种物品都有无限件可用。 第 $i$ 种物品的体积是 $v_i$。 现需要计算：有多少种不同的选择物品的方案，可以使得**恰好装满**背包（即所选物品的总体积**等于** $V$）？ **注意**： 1. 两种方案不同当且仅当它们选择的**物品组合**不同（即每种物品选取的数量不同） 2. 物品的选取顺序不影响方案计数（只考虑组合，不考虑排列） 3. 每种物品可以选择任意多件（只要总体积不超过背包容量）

第一行两个整数 $N$，$V$，用空格隔开，分别表示物品种数和背包容积。 接下来有 $N$ 行，每行一个整数 $v_i$，表示第 $i$ 种物品的体积。

输出一个整数，表示恰好装满背包的方案数对 $10^9 + 7$ 取模的结果。 如果没有任何方案可以恰好装满背包，输出 `0`。

### 样例解释 #1 容量为5，物品体积分别为1、2、3，共有5种不同的方案： - 5个1：1+1+1+1+1 - 3个1和1个2：1+1+1+2 - 1个1和2个2：1+2+2 - 2个1和1个3：1+1+3 - 1个2和1个3：2+3 ### 样例解释 #2 容量为4，物品体积分别为2和3，只有1种方案：2+2 ### 样例解释 #3 容量为5，物品体积分别为2和4，无法恰好装满，输出0 **数据范围** * $0 < N, V \leq 10^3$ * $0 < v_i \leq 10^3$ **取模要求**： * 模数 $M = 10^9 + 7$ * 在动态规划过程中，每进行一次加法运算后都应对 $M$ 取模 **注意**： 1. 本题计算的是**组合数**（不同物品的选取数量），而非排列数 2. 每种物品有无限件可用 3. 物品的输入顺序不影响计数结果（但通常我们会按某种顺序进行DP）