题目描述

有一串由 $n$ 个珠子构成的环形珠链。

珠链上的每个珠子要么是黑色要么是白色，每个珠子都能感应到它左边的 $k$ 个珠子以及右边的 $k$个珠子。

每一秒珠子都会尝试改变自己的颜色，对于一个珠子，如果它感应到的 $2k$ 个珠子中有奇数个是黑色，那么它会改变自己的颜色，否则它会保持自己原来的状态。并且所有要改变颜色的珠子都会在同一时刻改变自己的颜色。

由于珠链是环形的，因此，对于两条珠链，如果其中一条可以通过旋转变成另外一条，那么这两条珠链是本质相同的。

给出 $n,k,t$ 以及一条长度为 $n$ 的珠链的珠子的颜色，问有多少条本质不同的珠链能够在 $t$ 秒之后变成给出的珠链。

输入格式

第一行给出数据组数 $T$。

下面每组数据，先给出一行三个整数 $n,k,t$，再一行给出 $n$ 个字符描述每颗珠子的初始颜色。

输出格式

一行一个整数，表示答案在对 $9973$ 取模意义下的值。

3 
6 1 1 
bbbwww 
6 1 1 
bwbbww 
12 2 1 
bbwwwbwwwwww 

4 
0 
1 

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 200$，$1\leq k\leq \frac{n-1}{2}$，$0\leq t\leq 200$，$1\leq T\leq 20$。