Reverse and Concatenate

题意翻译

给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$。定义 $rev(s)$ 为将 $s$ 反转后得到的字符串。你可以执行**恰好** $k$ 次操作，每次操作你可以将 $s$ 替换为 $s+rev(s)$ 或 $rev(s)+s$（其中 $+$ 为拼接操作），求在恰好 $k$ 次操作之后得到的字符串一共有多少种。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 100$。 - $1\leqslant n\leqslant 100$，$0\leqslant k\leqslant 1000$。 Translated by Eason_AC 2022.2.9

题目描述

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.

输入输出样例

输入样例 #1

4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab

输出样例 #1

2
2
1
1

说明

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.