ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

NEERC 2012, Eastern subregional contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Titan Ruins: Waiting for Stability

Time limit: 1.0 second
Memory limit: 64 MB
`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 ≤ xijn). 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 stable coins.


Output the remainder in division of the number of different suitable parts of stacks by 109 + 7.


7 3
3 3 2 2
3 4 5 5
1 7
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
To submit the solution for this problem go to the Problem set: 1916. Titan Ruins: Waiting for Stability