// Arup Guha
// 2/7/2019
// Solution to 2019 Proposed Mercer Problem: Lollathon

import java.util.*;

public class lollathon_arup {
	
	final public static int MOD = 10007;
	
	public static void main(String[] args) {
		
		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();
		
		// Process each case.
		for (int loop=0; loop<numCases; loop++) {
			
			// Get the input.
			int n = stdin.nextInt();
			int lolSize = stdin.nextInt();
			char[] text = stdin.next().toCharArray();
			
			// Physically form the LOL string.
			char[] pattern = formLOL(lolSize);
			
			// Solve the problem using DP pretty similar to the textbook LCS solution.
			System.out.println(lcsCnt(text, pattern));
		}
	}
	
	// Returns a char array witn n L's, 1 O, and n L's.
	public static char[] formLOL(int n) {
		char[] res = new char[2*n+1];
		Arrays.fill(res, 'L');
		res[n] = 'O';
		return res;
	}
	
	public static int lcsCnt(char[] text, char[] pattern) {
		
		// So I don't have to type these.
		int tLen = text.length, pLen = pattern.length;
		
		// There is one way to match 0 pattern letters with any number of text letters.
		int[][] dp = new int[tLen+1][pLen+1];
		for (int i=0; i<=tLen; i++) dp[i][0] = 1;
		
		// Usual row/col ordering for most DPs.
		for (int i=1; i<=tLen; i++) {
			for (int j=1; j<=pLen; j++) {
				
				// We can match these letters, if we want, or we can NOT match them.
				if (text[i-1] == pattern[j-1])
					dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%MOD;
				
				// Otherwise, we can only NOT match the letters.	
				else
					dp[i][j] = dp[i-1][j];
			}
		}
		
		// This is the answer we want.
		return dp[tLen][pLen];
	}
}