E2. Искорка и древний свиток (усложненная версия)
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

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

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$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$$$).