F. Osama's Birthday
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Osama is the biggest flower of all flowers, so on his birthday, Ahmad will gift him an endless amount of flowers <3.

Ahmad gave him $$$n$$$ bouquets of flowers. Each bouquet has some types of flowers in it, and there exists an infinite amount of each type of flowers.

Osama has a garden of length $$$m$$$, so he needs to fill it with $$$m$$$ flowers. He will fill it in the following way:

  • He will first choose a bouquet of flowers (he can't change it after selecting it);
  • Then he will select each of the $$$m$$$ flowers from this bouquet.

What is the number of distinct gardens he can make using the above strategy? Since the answer is huge, you have to print it modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 5)$$$ – the number of test cases.

The first line of each case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 19;\space 1 \leq m \leq 10^9)$$$.

The next $$$n$$$ lines start with an integer $$$k$$$ $$$(1 \leq k \leq 60)$$$, then follow $$$k$$$ distinct integers $$$a_1, a_2, \ldots, a_k$$$ $$$(1 \leq a_i \leq 60)$$$.

Output

For each test case, print an integer, the number of distinct gardens Osama can make modulo $$$10^9 + 7$$$.

Example
Input
2
2 2
2 2 3
2 1 2
3 4
3 1 2 3
3 3 4 5
3 4 5 6
Output
7
226
Note

The different gardens he can make in the first case are: $$$[\{1, 1\}, \{1, 2\}, \{2, 1\}, \{2, 2\}, \{2, 3\}, \{3, 2\}, \{3, 3\}]$$$