Mirko 在他的阁楼里找到了 $N$ 个装有各种被遗忘玩具的盒子。一共有 $M$ 种不同的玩具，编号为 $1$ 到 $M$，但每种玩具可以多次出现在不同的盒子中。

Mirko 决定选择一些盒子，使得每种玩具都至少出现一次，然后把其余的盒子扔掉。

求 Mirko 选择盒子的方案数。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 1\,000\,000$，$1 \le M \le 20$）。

接下来的 $N$ 行，每行包含一个整数 $K_i$（$0 \le K_i \le M$），紧接着是 $K_i$ 个互不相同的介于 $[1, M]$ 之间的整数，表示该盒子中的玩具。

输出格式

输出的第一行也是唯一的一行，包含所求的方案数模 $1\,000\,000\,007$ 的结果。

子任务

在占总分 $50\%$ 的测试数据中，满足 $N \le 100$ 且 $M \le 15$。

在占总分 $70\%$ 的测试数据中，满足 $N \le 1\,000\,000$ 且 $M \le 15$。

样例

输入样例 1

3 3
3 1 2 3
3 1 2 3
3 1 2 3

输出样例 1

7

输入样例 2

3 3
1 1
1 2
1 3

输出样例 2

1

输入样例 3

4 5
2 2 3
2 1 2
4 1 2 3 5
4 1 2 4 5

输出样例 3

6