29217번 - Шрам готовит атаку 다국어

Шрам готовит армию гиен для нападения. На отбор пришло $n$ гиен. Шрам желает выбрать самых способных из них: тех, кому природа подарила прирожденный талант.

У каждой гиены есть свой генотип. Генотип представляет из себя последовательность генов. Гены обозначены строчными латинскимим буквами.

Некоторая непустая подпоследовательность генов генотипа каждой гиены являлась ее генотипом при рождении. После этого, за время жизни гиены в различные места генотипа могло добавиться произвольное количество произвольных генов, после чего он пришел к нынешнему своему виду.

Скажем, что генотип $a$ мощнее генотипа $b$, если существует такой индекс $i$, что для всех $j < i$ $a_j = b_j$, а $a_i$ идет в алфавите раньше, чем $b_i$. Если для всех $i$ $a_i = b_i$, то мощнее тот генотип, в котором меньше генов.

Шраму стало интересно, какие генотипы могли быть при рождении у каждой гиены, если известно, что при рождении генотип $i$-ой гиены был мощнее, чем генотип $(i+1)$-ой. Определите число вариантов наборов начальных генотипов гиен, удовлетворяющих всем описанным условиям, взятое по модулю 1{\,}000{\,}000{\,}007.

В самой первой строке написано число $n$ --- число гиен($1 \le n \le 10$). Дальше следует $n$ строк, в каждой из которой записана строка $s_i$, обозначающая генотип $i$-ой гиены в данный момент. Длина каждой строки не превосходит 13.

Выведите ответ на задачу по модулю $1\,000\,000\,007$.