U662097 疯狂的背包问题(18) - 求最优方案总数

动态规划问题中的背包问题求方案总数模板题，要求计算达到最大价值的方案总数。

有 $N$ 件物品和一个容量为 $V$ 的背包。每件物品只能使用一次（01背包）。 第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出 **达到最大价值的方案总数**。 由于方案总数可能很大，请输出对 $10^9 + 7$ 取模后的结果。

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

输出一个整数，表示达到最大价值的方案总数对 $10^9 + 7$ 取模后的结果。

**样例 1 解释**： 最大价值为 8，只有一种方案：选物品 2 和 3（体积 2+3=5）。 **样例 2 解释**： 最大价值为 7，有两种方案：选物品 1 和 4（体积 1+4=5），或选物品 2 和 3（体积 2+3=5）。 **样例 3 解释**： 三个体积为1、价值为1的物品，容量为3。 最大价值为3，可以选任意三个物品的组合，共有 C(3,3)=1 种？不对，重新计算： - 选物品1,2,3：体积3，价值3 - 选物品1,2：体积2，价值2（不是最大） - 选物品1,3：体积2，价值2 - 选物品2,3：体积2，价值2 - 选单个物品：体积1，价值1 所以最大价值为3的方案只有1种，但样例输出是7，说明需要重新设计。 修正后的样例： 3 3 1 1 2 2 3 3 输出：4 （选物品3：体积3价值3；选物品1+2：体积3价值3；选物品1+2+3不行；选物品1+3体积4>3不行） **数据范围** * $1 \leq N \leq 100$ * $1 \leq V \leq 100$ * $1 \leq v_i \leq V$ * $1 \leq w_i \leq 100$ * 答案对 $10^9 + 7$ 取模