{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp style\u003d\"margin-left: 16.55pt;\"\u003e\r\n\tYou are given a string \u003cstrong\u003eS\u003c/strong\u003e of length \u003cstrong\u003eN\u003c/strong\u003e. Can you find a string \u003cstrong\u003eP\u003c/strong\u003e which satisfies the following conditions?\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 34.55pt;\"\u003e\r\n\t1. Length of \u003cstrong\u003eP\u003c/strong\u003e will be \u003cstrong\u003eN\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 34.55pt;\"\u003e\r\n\t2. Distance between \u003cstrong\u003eS \u003c/strong\u003eand \u003cstrong\u003eP\u003c/strong\u003e will be less than or equal to \u003cstrong\u003eK\u003c/strong\u003e\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 34.55pt;\"\u003e\r\n\t3. \u003cstrong\u003eP\u003c/strong\u003e will be a palindrome.\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 34.55pt;\"\u003e\r\n\t4. \u003cstrong\u003eP\u003c/strong\u003e can contain only characters \u0026lsquo;a\u0026rsquo;, \u0026lsquo;b\u0026rsquo;, \u0026hellip;, \u0026lsquo;z\u0026rsquo;\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 16.55pt;\"\u003e\r\n\tYou have to calculate, in how many ways you can choose \u003cstrong\u003eP\u003c/strong\u003e. This number can be very large, so print the answer modulo 1000000000 (10\u003csup\u003e9\u003c/sup\u003e).\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 16.55pt;\"\u003e\r\n\t\u003cu\u003eNotes:\u003c/u\u003e\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 34.55pt;\"\u003e\r\n\t-\u0026nbsp; A string is a sequence of characters. For this problem consider that all strings can contain only \u0026lsquo;a\u0026rsquo;, \u0026lsquo;b\u0026rsquo;, \u0026hellip;, \u0026lsquo;z\u0026rsquo;, i.e. 26 available characters.\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 34.55pt;\"\u003e\r\n\t-\u0026nbsp; The length of the string is defined by the number of characters in the string. For example, length of \u0026ldquo;abcba\u0026rdquo; is 5.\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 34.55pt;\"\u003e\r\n\t-\u0026nbsp; A string is called palindrome when it is the same string when written from forwards or backwards. For example \u0026ndash; \u0026ldquo;abcba\u0026rdquo;, \u0026ldquo;abba\u0026rdquo;, \u0026ldquo;a\u0026rdquo; are palindrome but \u0026ldquo;abc\u0026rdquo; is not a palindrome.\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 34.55pt;\"\u003e\r\n\t-\u0026nbsp; Distance between two string of same length is the number of mismatches of corresponding characters. For example, distance between \u0026ldquo;abcb\u0026rdquo; and \u0026ldquo;bcba\u0026rdquo; is 4 because no character of first string matches to the character of the corresponding index of second string, but distance between \u0026ldquo;abc\u0026rdquo; and \u0026ldquo;cba\u0026rdquo; is 2.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tInput starts with an integer \u003cstrong\u003e\u003cem\u003eT \u003c/em\u003e\u003c/strong\u003e(T is around 5000), the number of test cases.\u003c/p\u003e\r\n\u003cp style\u003d\"margin-left: 16.55pt;\"\u003e\r\n\tEach test case consists of two lines. First line contains two integers \u003cstrong\u003eN\u003c/strong\u003e(1\u0026le;N\u0026le;1000) and \u003cstrong\u003eK\u003c/strong\u003e (0\u0026le;K\u0026le;1000). Second line contains a string \u003cstrong\u003eS\u003c/strong\u003e of length \u003cstrong\u003eN\u003c/strong\u003e. \u003cstrong\u003eS\u003c/strong\u003e contains only characters from \u0026lsquo;a\u0026rsquo;, \u0026lsquo;b\u0026rsquo;, \u0026hellip;, \u0026lsquo;z\u0026rsquo;.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp style\u003d\"margin-left: 16.55pt;\"\u003e\r\n\tFor each test case output the number of test cases followed by the number of ways the string can be chosen modulo 1000000000 (10\u003csup\u003e9\u003c/sup\u003e). See sample output for exact format.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t\u003cspan style\u003d\"font-family: courier new,courier,monospace;\"\u003e3\u003cbr /\u003e\r\n\t3 2\u003cbr /\u003e\r\n\tkxk\u003cbr /\u003e\r\n\t4 1\u003cbr /\u003e\r\n\taddc\u003cbr /\u003e\r\n\t4 3\u003cbr /\u003e\r\n\tAddc\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tCase 1: 51\u003cbr /\u003e\r\n\tCase 2: 2\u003cbr /\u003e\r\n\tCase 3: 76\u003c/p\u003e"}}]}