T4 年货采购（purchase）

题目描述

年货节到了，商场里有 $n$ 类商品。第 $i$ 类商品有 $m_i$ 件不同的商品，它们的价格分别为 $c_{i,1}, c_{i,2}, \dots, c_{i,m_i}$。

你的购物规则是：对于每一类商品，最多购买其中一件（也可以一件都不买）。你希望恰好花掉 $W$ 元。

输入文件 purchase.in，输出文件 purchase.out。

请你计算一共有多少种不同的购买方案，答案对 $10^9+7$ 取模。两种方案不同，当且仅当它们在某一类里买了不同的商品（或一类买了而另一类没买）。

输入格式

输入第一行包含两个正整数 $n,W$。

接下来 $n$ 行，每行描述一类商品：先一个整数 $m_i$，随后 $m_i$ 个正整数 $c_{i,j}$，表示该类商品的件数与价格。

输出格式

输出一行一个整数，表示方案数对 $10^9+7$ 取模后的结果。

样例 1 输入

3 6
2 2 3
2 1 4
2 2 5

样例 1 输出

4

样例 1 解释

三类可选金额分别为 $\{2,3\}$、$\{1,4\}$、$\{2,5\}$（不买视为金额 $0$）。恰好凑出 $6$ 元的方案有：$(2,4,0)$、$(0,4,2)$、$(3,1,2)$、$(0,1,5)$，共 $4$ 种。

样例 2 输入

1 3
2 1 2

样例 2 输出

0

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 6$。
• 对于 $100\%$ 的数据，保证 $1 \le n \le 100$，$1 \le W \le 2000$，$1 \le m_i \le 20$，$1 \le c_{i,j} \le W$。