CF1634A Reverse and Concatenate

Real stupidity beats artificial intelligence every time. — Terry Pratchett, Hogfather, Discworld You are given a string $ s $ of length $ n $ and a number $ k $ . Let's denote by $ rev(s) $ the reversed string $ s $ (i.e. $ rev(s) = s_n s_{n-1} ... s_1 $ ). You can apply one of the two kinds of operations to the string: - replace the string $ s $ with $ s + rev(s) $ - replace the string $ s $ with $ rev(s) + s $ How many different strings can you get as a result of performing exactly $ k $ operations (possibly of different kinds) on the original string $ s $ ? In this statement we denoted the concatenation of strings $ s $ and $ t $ as $ s + t $ . In other words, $ s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m $ , where $ n $ and $ m $ are the lengths of strings $ s $ and $ t $ respectively.

The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — number of test cases. Next $ 2 \cdot t $ lines contain $ t $ test cases: The first line of a test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 100 $ , $ 0 \le k \le 1000 $ ) — the length of the string and the number of operations respectively. The second string of a test case contains one string $ s $ of length $ n $ consisting of lowercase Latin letters.

For each test case, print the answer (that is, the number of different strings that you can get after exactly $ k $ operations) on a separate line. It can be shown that the answer does not exceed $ 10^9 $ under the given constraints.

In the first test case of the example: After the first operation the string $ s $ can become either aabbaa or baaaab. After the second operation there are 2 possibilities for $ s $ : aabbaaaabbaa and baaaabbaaaab.