U663733 疯狂的背包问题(7) - 完全背包问题（计数排列问题）

动态规划问题中的完全背包问题变体，本题考察的是**考虑顺序的方案计数**。

有 $N$ 种物品和一个容量是 $V$ 的背包。每种物品都有无限件可用。 第 $i$ 种物品的体积是 $v_i$。 现需要计算：有多少种不同的**放入顺序**，可以使得在依次放入物品的过程中，背包恰好被装满（即放入最后一个物品后，背包内物品的总体积**等于** $V$）？ **注意**： 1. 两种方案不同当且仅当它们**放入物品的顺序不同**（即使最终选取的各种物品数量相同，只要顺序不同，就视为不同的方案） 2. 每种物品有无限件可用，即同一个种类的物品可以在一个方案中重复使用多次 3. 在放入过程中，**任何时候的总体积都不能超过背包容量**（即放入每个物品后，当前体积 ≤ V） 4. 只有最后一次放入后，总体积**恰好等于** V 才计入方案

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

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

### 样例解释 #1 容量为4，物品体积分别为1、2、3，共有7种不同的放入顺序： **用四个1：** 1-1-1-1（1种） **用两个1和一个2：** 1-1-2, 1-2-1, 2-1-1（3种） **用一个1和一个3：** 1-3, 3-1（2种） **用两个2：** 2-2（1种） 总计：1 + 3 + 2 + 1 = 7种 ### 样例解释 #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. 物品的输入顺序不影响计数结果