Вася увлекся биоинформатикой. Он собирается написать статью про похожие циклические последовательности ДНК, и поэтому он придумал новый способ определения схожести циклических последовательностей.
Пусть строки s и t имеют одинаковую длину n, тогда функция h(s, t) определяется как количество позиций, в которых соответствующие символы s и t совпадают. При помощи функции h(s, t), определяется функция расстояния по Василию ρ(s, t):
где
— это строка
s, циклически сдвинутая на
i символов влево. Например,
ρ("AGC", "CGT") = h("AGC", "CGT") + h("AGC", "GTC") + h("AGC", "TCG") + h("GCA", "CGT") + h("GCA", "GTC") + h("GCA", "TCG") + h("CAG", "CGT") + h("CAG", "GTC") + h("CAG", "TCG") = 1 + 1 + 0 + 0 + 1 + 1 + 1 + 0 + 1 = 6Вася нашел в интернете строку s длины n. Теперь он хочет посчитать количество строк t, находящихся на максимальном расстоянии по Василию от строки s. Формально говоря, t должна удовлетворять равенству: 
.
Вася не смог перебрать все возможные строки для нахождения ответа, поэтому ему нужна ваша помощь. Поскольку ответ может быть очень большим, посчитайте количество подходящих строк по модулю 109 + 7.
Выходные данные
Выведите одно число — ответ по модулю 109 + 7.
Примечание
Обратите внимание, что если для двух различных строк t1 и t2 значения ρ(s, t1) и ρ(s, t2) являются максимальными среди всех возможных строк, то обе строки необходимо учесть в итоговом количестве даже в том случае, когда одну из них можно получить циклическим сдвигом из другой.
В первом примере существует ρ("C", "C") = 1, для остальных строк t длины 1 значение ρ(s, t) равно 0.
Во втором примере ρ("AG", "AG") = ρ("AG", "GA") = ρ("AG", "AA") = ρ("AG", "GG") = 4.
В третьем примере ρ("TTT", "TTT") = 27.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
C
|
1
|
|
2
|
2
AG
|
4
|
|
3
|
3
TTT
|
1
|