Юля проводит эксперимент в своей лаборатории. Она поместила несколько колоний светящихся бактерий в горизонтальную пробирку. Бактерии разного типа можно отличить по цвету. Юля обозначает типы бактерий маленькими латинскими буквами «a», ..., «z».

Пробирка разделена на n областей, расположенных в ряд друг за другом. В каждый момент времени любая область занята ровно одной колонией бактерий определенного типа. Таким образом, популяцию пробирки в любой момент можно описать строкой из n латинских букв.

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

В качестве примера рассмотрим пробирку с популяцией «babb». Для следующей атаки существует шесть вариантов:

• первая колония атакует вторую (1 → 2), в результате популяция будет выглядеть как «bbbb»;
• 2 → 1, результат «aabb»;
• 2 → 3, результат «baab»;
• 3 → 2, результат «bbbb» (в данном случае результат такой же, как и в первом варианте);
• 3 → 4 или 4 → 3, популяция не меняется.

Предсказать последовательность нападений довольно трудно. Юля интересуется, сколько способов расположения бактерий в пробирке может получится после некоторой последовательности нападений (при этом возможно, что нападений не будет совсем). Поскольку ответ может быть большим, найдите его по модулю 10⁹ + 7.