Это более сложная версия задачи E с большими ограничениями.

Сумеречная Искорка получила новое задание от принцессы Селестии. В этот раз Искорке нужно расшифровать древний свиток, содержащий важные знания о происхождении пони.

Чтобы скрыть важнейшую информацию от злых глаз, старейшины пони заколдовали свиток. Заклинание вставляет ровно одну букву в любое место каждого словa, к которому оно применено. Чтобы сделать путь к знанию более запутанным, старейшины выбрали некоторые из слов свитка и применили к ним заклинание.

Сумеречная Искорка знает, что старейшины во всем почитали порядок, поэтому изначально свиток содержал слова в лексикографически неубывающем порядке. Искорке нужно удалить по одной букве из некоторых слов в свитке (чтобы отменить заклинание), для того чтобы получить какую-то версию изначального свитка.

К сожалению, Искорка не всегда может однозначно восстановить древний свиток. Чтобы не упустить важные знания, ей придется перебрать все варианты изначального свитка и найти нужный. Чтобы оценить максимальное время, которое Искорка потратит на работу, ей нужно знать количество вариантов, которые ей нужно перебрать. Она просит вас найти это количество! Так как это количество может быть слишком большим, Искорке достаточно лишь знать его по модулю $$$10^9+7$$$, остальную часть она сможет оценить сама.

Могло случиться так, что принцесса Селестия отправила неверный свиток, и Искорка не сможет получить никакую версию изначального свитка.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

• $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$;
• в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.