Codeforces Round 662 (Div. 2) |
---|
Закончено |
Это более сложная версия задачи E с большими ограничениями.
Сумеречная Искорка получила новое задание от принцессы Селестии. В этот раз Искорке нужно расшифровать древний свиток, содержащий важные знания о происхождении пони.
Чтобы скрыть важнейшую информацию от злых глаз, старейшины пони заколдовали свиток. Заклинание вставляет ровно одну букву в любое место каждого словa, к которому оно применено. Чтобы сделать путь к знанию более запутанным, старейшины выбрали некоторые из слов свитка и применили к ним заклинание.
Сумеречная Искорка знает, что старейшины во всем почитали порядок, поэтому изначально свиток содержал слова в лексикографически неубывающем порядке. Искорке нужно удалить по одной букве из некоторых слов в свитке (чтобы отменить заклинание), для того чтобы получить какую-то версию изначального свитка.
К сожалению, Искорка не всегда может однозначно восстановить древний свиток. Чтобы не упустить важные знания, ей придется перебрать все варианты изначального свитка и найти нужный. Чтобы оценить максимальное время, которое Искорка потратит на работу, ей нужно знать количество вариантов, которые ей нужно перебрать. Она просит вас найти это количество! Так как это количество может быть слишком большим, Искорке достаточно лишь знать его по модулю $$$10^9+7$$$, остальную часть она сможет оценить сама.
Могло случиться так, что принцесса Селестия отправила неверный свиток, и Искорка не сможет получить никакую версию изначального свитка.
Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество слов в свитке. $$$i$$$-я из следующих $$$n$$$ строк содержит строку, состоящую из строчных букв латинского алфавита — $$$i$$$-е слово свитка. Длина каждого слова хотя бы один. Суммарная длина всех слов не превосходит $$$10^6$$$.
Выведите одно целое число — количество вариантов получить версию оригинала из свитка по модулю $$$10^9+7$$$.
3 abcd zaza ataka
4
4 dfs bfs sms mms
8
3 abc bcd a
0
6 lapochka kartyshka bigbabytape morgenshtern ssshhhiiittt queen
2028
Заметьте, что старейшины могли написать пустое слово (но тогда они точно применили к нему заклинание, и таким образом это слово теперь имеет длину $$$1$$$).
Название |
---|