Question
Magical String Transformations
In the kingdom of Valoria, young mage Aiden was given a magical scroll by the Grand Wizard. The scroll contained a powerful string spell called “Reversia.” Aiden was tasked with taking a string S of length N and transforming it exactly K times using one of two ancient spells:
- He could extend the string by appending its reverse, creating a new string: S + fun(S).
- Alternatively, he could reverse the string and prepend it, forming: fun(S) + S.
Input
The first line of the input contains two space-separated integers, N and K.
The second line of the input contains the string S, of length N.
Constraints
1 ≤ N ≤ 105
0 ≤ K ≤ 109
The second line of the input contains the string S, of length N.
Constraints
1 ≤ N ≤ 105
0 ≤ K ≤ 109
Output
Print the total number of possible different strings that can be obtained after K such operations.
Example
Sample Input
3 1
abc
Sample Output
2
Explanation
After applying the operations one time, we can get the following strings:
abccba,
cbaabc
It can be verified that no more kinds of strings can be obtained.
3 1
abc
Sample Output
2
Explanation
After applying the operations one time, we can get the following strings:
abccba,
cbaabc
It can be verified that no more kinds of strings can be obtained.