ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1916. Руины титанов: в ожидании стабильности

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
«Час от часу не легче», — произнёс Сорен, когда они с Альбой зашли в комнату с до боли знакомыми монетами. Однако в этот раз что-то было немного не так, как раньше. Во-первых, все монеты лежали в аккуратных стопочках. А во-вторых, с разных сторон то и дело слышались какие-то лёгкие хлопки. Сорен заметил, что во многих монетах чувствуется магическая энергия и сама сущность этих монет неустойчива. Достаточно лёгкого воздействия, чтобы такая монета исчезла, но вместо неё в таком случае может появиться несколько новых. Некоторые из новых монет при этом уже не несут никакой магической энергии и совершенно устойчивы, а некоторые — всё ещё неустойчивы, и могут точно так же исчезнуть, создав новые.
Изучив лежащую на столе книгу, Альба узнал, что неустойчивые монеты бывают всего нескольких видов, и монеты одного вида преобразуются всегда одинаково. Более того, если неустойчивая монета в момент исчезновения лежит в стопке, то лежащие на ней монеты подпрыгивают, а приземляются уже на монеты, появившиеся вместо исчезнувшей.
На одной из стен нашлось вертикальное углубление шириной как раз с монету. Сорен предположил, что для того, чтобы двери открылись, нужно заполнить это углубление стопкой монет. Вот только каких? Было понятно, что нельзя класть неустойчивые — их преобразования могут привести к непредсказуемым эффектам. Подумав, друзья решили, что самым логичным было бы подождать пока одна неустойчивая монета превратится в стопку устойчивых, взять несколько подряд идущих монет из этой стопки и положить в углубление. Проблема в том, что количество различных способов заполнить углубление будет огромным. Или нет?

Исходные данные

В первой строке даны два числа: n — количество видов монет и k — число монет, влезающих в углубление (2 ≤ n, k ≤ 100). В i-й из следующих строк описан i-й вид монет. Если он устойчив, то там записано число −1. Иначе сначала идёт число ki — количество монет, в которые преобразуется i-й вид монет, затем через пробел ki целых чисел xij — виды монет, перечисленные в порядке от нижней к верхней в появляющейся стопке (1 ≤ ki ≤ 100; 1 ≤ xijn). Сумма всех 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, Четвертьфинал Восточного подрегиона