`Things are going from bad to worse,' Soren said when he and Alba entered a
room with painfully familiar coins. This time something was a bit different.
All the coins were arranged into neat stacks, and strange soft claps were heard
from time to time. Soren felt that the coins contained magic power and some of
them were unstable. A slight impulse was enough to make such a coin transform
into several new coins. Some of the new coins had no magic power and were
absolutely stable, while others were unstable and could transform in
the same manner.
Having studied the book lying on the table, Alba learned that there were only
several types of unstable coins and that coins of the same type always
transformed in the same way. When an unstable coin transformed all
the coins above it were pushed up and placed on top of the new coins.
One of the walls had a vertical cavity exactly one coin wide. Soren conjectured
that the door would open if the cavity was filled with a stack of coins. But
which coins? Alba and Soren understood that they couldn't put unstable coins
into the cavity, because their transformations might cause unpredictable
effects. They decided to wait until one of the unstable coins turned into a
stack of stable coins, take several consecutive coins from this stack, and put
them into the cavity. But first they wanted to know the number of different
ways to fill the cavity in this way.
The first line contains the number n of coin types and the number k of coins in a stack that can fill the cavity (2 ≤ n, k ≤ 100). The i-th of the following lines describes the i-th type of coins.
If the type is stable, the line contains the number −1. Otherwise, the line starts with the number
ki of coins into which a coin of type i transforms. After this number, there are ki integers xij,
which describe the appearing stack (1 ≤ ki ≤ 100; 1 ≤ xij ≤ n).
The integers xij are the types of coins in this stack from bottom to top.
The sum of all ki does not exceed 100.
It is guaranteed that any unstable coin will eventually transform into a stack of
Output the remainder in division of the number of different suitable parts of
stacks by 109 + 7.
3 3 2 2
3 4 5 5
3 7 7 7
A coin of type 3 produces one coin of type 7.
A coin of type 2 produces a stack 4-5-5.
From a coin of type 1, in the end we obtain a stack 7-4-5-5-4-5-5,
and a coin of type 6 produces a stack 7-7-7.
Therefore, all possible parts of stacks of height 3 are 7-7-7, 4-5-5, 7-4-5, 5-5-4, and 5-4-5.
Problem Author: Ivan Burmistrov (prepared by Dmitry Ivankov)
Problem Source: NEERC 2012, Eastern subregional contest