Real stupidity beats artificial intelligence every time.
— Terry Pratchett, Hogfather, Discworld
Вам дана строка \(s\) длины \(n\) и число \(k\). Обозначим за \(rev(s)\) развёрнутую строку \(s\) (т.е. \(rev(s) = s_n s_{n-1} ... s_1\)). Вы можете выполнять два типа операций:
- заменить строку \(s\) на \(s + rev(s)\)
- заменить строку \(s\) на \(rev(s) + s\)
После выполнения ровно \(k\) операций (возможно, различных) над строкой, какое количество различных строк вы можете получить из начальной строки \(s\)?
Мы обозначили конкатенацию строк \(s\) и \(t\) как \(s + t\). Другими словами, \(s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m\), где \(n\) и \(m\) - длины строк \(s\) и \(t\) соответственно.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите количество различных строк, которые вы можете получить после применения ровно \(k\) операций.
Можно показать, что при данных ограничениях ответ не превосходит \(10^9\).
Примечание
Рассмотрим первый набор входных данных:
После первой операции строка \(s\) может стать либо aabbaa, либо baaaab. После второй операции \(s\) может принимать только такие 2 значения: aabbaaaabbaa и baaaabbaaaab.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab
|
2
2
1
1
|