«Час от часу не легче», — произнёс Сорен, когда они с Альбой зашли в комнату с
до боли знакомыми монетами. Однако в этот раз что-то было немного не так,
как раньше. Во-первых, все монеты лежали в аккуратных стопочках. А во-вторых, с разных
сторон то и дело слышались какие-то лёгкие хлопки. Сорен заметил, что во
многих монетах чувствуется магическая энергия и сама сущность этих монет неустойчива.
Достаточно лёгкого воздействия, чтобы такая монета исчезла, но вместо неё в таком случае
может появиться несколько новых. Некоторые из новых монет при этом уже не несут
никакой магической энергии и совершенно устойчивы, а некоторые — всё ещё неустойчивы,
и могут точно так же исчезнуть, создав новые.
Изучив лежащую на столе книгу, Альба узнал, что неустойчивые монеты бывают всего
нескольких видов, и монеты одного вида преобразуются всегда одинаково. Более
того, если неустойчивая монета в момент исчезновения лежит в стопке, то
лежащие на ней монеты подпрыгивают, а приземляются уже на монеты, появившиеся
вместо исчезнувшей.
На одной из стен нашлось вертикальное углубление шириной как раз с монету. Сорен
предположил, что для того, чтобы двери открылись, нужно заполнить это углубление
стопкой монет. Вот только каких? Было понятно, что нельзя класть
неустойчивые — их преобразования могут привести к непредсказуемым эффектам.
Подумав, друзья решили, что самым
логичным было бы подождать пока одна неустойчивая монета превратится в стопку устойчивых,
взять несколько подряд идущих монет из этой стопки и положить в углубление.
Проблема в том, что количество различных способов заполнить углубление будет огромным. Или нет?
Исходные данные
В первой строке даны два числа: n — количество видов монет и k — число монет,
влезающих в углубление (2 ≤ n, k ≤ 100).
В i-й из следующих строк описан i-й вид монет.
Если он устойчив, то там записано число −1. Иначе сначала идёт число
ki — количество монет, в которые преобразуется i-й вид монет, затем через
пробел ki целых
чисел xij — виды монет, перечисленные в порядке от нижней
к верхней в появляющейся стопке (1 ≤ ki ≤ 100; 1 ≤ xij ≤ n).
Сумма всех ki не превосходит 100. Гарантируется, что любая
неустойчивая монета рано или поздно преобразуется в некоторое количество
устойчивых.
Результат
Выведите единственное целое число — остаток от деления на 109 + 7 количества
подходящих стопок.
Пример
исходные данные | результат |
---|
7 3
3 3 2 2
3 4 5 5
1 7
-1
-1
3 7 7 7
-1
| 5
|
Замечания
Из третьего вида монет получается одна монета 7.
Из второго вида монет получается стопка 4-5-5. Из первого вида в итоге получается 7-4-5-5-4-5-5.
Из шестого — 7-7-7. То есть, все возможные части стопок размером в три монеты — это 7-7-7, 4-5-5, 7-4-5, 5-5-4 и 5-4-5.
Автор задачи: Иван Бурмистров (подготовка - Дмитрий Иванков)
Источник задачи: NEERC 2012, Четвертьфинал Восточного подрегиона