Юля проводит эксперимент в своей лаборатории. Она поместила несколько колоний светящихся бактерий в горизонтальную пробирку. Бактерии разного типа можно отличить по цвету. Юля обозначает типы бактерий маленькими латинскими буквами «a», ..., «z».
Пробирка разделена на n областей, расположенных в ряд друг за другом. В каждый момент времени любая область занята ровно одной колонией бактерий определенного типа. Таким образом, популяцию пробирки в любой момент можно описать строкой из n латинских букв.
Иногда какая-то из колоний может решить захватить другую колонию в одной из соседних областей. В этом случае атакованная колония немедленно уничтожается и заменяется колонией того же типа, что и атакующая колония, при этом атакующая колония сохраняет свой тип. Колония может атаковать только соседей внутри пробирки. Одновременно может происходить не более одного нападения.
В качестве примера рассмотрим пробирку с популяцией «babb». Для следующей атаки существует шесть вариантов:
- первая колония атакует вторую (1 → 2), в результате популяция будет выглядеть как «bbbb»;
- 2 → 1, результат «aabb»;
- 2 → 3, результат «baab»;
- 3 → 2, результат «bbbb» (в данном случае результат такой же, как и в первом варианте);
- 3 → 4 или 4 → 3, популяция не меняется.
Предсказать последовательность нападений довольно трудно. Юля интересуется, сколько способов расположения бактерий в пробирке может получится после некоторой последовательности нападений (при этом возможно, что нападений не будет совсем). Поскольку ответ может быть большим, найдите его по модулю 109 + 7.
Примечание
В первом примере популяция не может измениться, поскольку все колонии имеют один и тот же тип.
Во втором примере возможны три конфигурации: «ab» (нападений не было), «aa» (первая колония захватила вторую) и «bb» (вторая колония захватила первую).
Для получения ответа на третий пример, помните, что могло произойти больше одного нападения.