{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nIn the kingdom of string, people like palindromic strings very much. They like only palindromic strings and dislike all other strings. There is a unified formula to calculate the score of a palindromic string. The score is calculated by applying the following three steps.\n\u003c/p\u003e\u003col\u003e\n\t\u003cli\u003eSince a palindromic string is symmetric, the second half(excluding the middle of the string if the length is odd) is got rid of, and only the rest is considered. For example, \"abba\" becomes \"ab\", \"aba\" becomes \"ab\" and \"abacaba\" becomes \"abac\".\u003c/li\u003e\n\t\u003cli\u003eDefine some integer values for \u0027a\u0027 to \u0027z\u0027.\u003c/li\u003e\n\t\u003cli\u003eTreat the rest part as a 26-based number \u003cvar\u003eM\u003c/var\u003e and the score is \u003cvar\u003eM\u003c/var\u003e modulo 777,777,777.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\nHowever different person may have different values for \u0027a\u0027 to \u0027z\u0027. For example, if \u0027a\u0027 is defined as 3, \u0027b\u0027 is defined as 1 and c is defined as 4, then the string \"accbcca\" has the score (3×26\u003csup\u003e3\u003c/sup\u003e+4×26\u003csup\u003e2\u003c/sup\u003e+4×26+1) modulo 777777777\u003d55537.\n\u003c/p\u003e\n\u003cp\u003e\nOne day, a very long string \u003cvar\u003eS\u003c/var\u003e is discovered and everyone in the kingdom wants to know that among all the palindromic substrings of S, what the one with the \u003cvar\u003eK\u003c/var\u003e-th smallest score is.\n\u003c/p\u003e\n\u003cp\u003e\n\u003c/p\u003e\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003e\nThe first line contains an integer \u003cvar\u003eT\u003c/var\u003e(1 ≤ \u003cvar\u003eT\u003c/var\u003e ≤ 20), the number of test cases.\n\u003c/p\u003e\n\u003cp\u003e\nThe first line in each case contains two integers \u003cvar\u003en, m\u003c/var\u003e(1 ≤ \u003cvar\u003en\u003c/var\u003e ≤ 100000, 1 ≤ \u003cvar\u003em\u003c/var\u003e ≤ 20) where \u003cvar\u003en\u003c/var\u003e is the length of \u003cvar\u003eS\u003c/var\u003e and \u003cvar\u003em\u003c/var\u003e is the number of people in the kingdom. The second line is the string \u003cvar\u003eS\u003c/var\u003e consisting of only lowercase letters. The next \u003cvar\u003em\u003c/var\u003e lines each containing 27 integers describes a person in the following format.\n\u003c/p\u003e\n\u003cp\u003e\n\u003cvar\u003eK\u003csub\u003ei\u003c/sub\u003e va vb ... vz\u003c/var\u003e\n\u003c/p\u003e\n\u003cp\u003e\nwhere \u003cvar\u003eva\u003c/var\u003e is the value of \u0027a\u0027 for the person, \u003cvar\u003evb\u003c/var\u003e is the value of \u0027b\u0027 and so on. It is ensured that the \u003cvar\u003eK\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e-th smallest palindromic substring exists and \u003cvar\u003eva, vb, ..., vz\u003c/var\u003e are in the range of [0, 26). But the values may coincide.\n\u003c/p\u003e\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003e\nFor each person, output the score of the \u003cvar\u003eK\u003c/var\u003e-th smallest palindromic substring in one line. Print a blank line after each case.\n\u003c/p\u003e\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n6 2\nabcdca\n3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n7 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0\n4 10\nzzzz\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n7 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 14\n51 4\nabcdefghijklmnopqrstuvwxyzyxwvutsrqponmlkjihgfedcba\n1 1 3 3 25 20 25 21 7 0 9 7 3 16 15 14 19 5 19 19 19 22 8 23 2 4 1\n25 1 3 3 25 20 25 21 7 0 9 7 3 16 15 14 19 5 19 19 19 22 8 23 2 4 1\n26 1 3 3 25 20 25 21 7 0 9 7 3 16 15 14 19 5 19 19 19 22 8 23 2 4 1\n76 1 3 3 25 20 25 21 7 0 9 7 3 16 15 14 19 5 19 19 19 22 8 23 2 4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n620\n\n14\n14\n14\n14\n14\n14\n14\n378\n378\n378\n\n0\n9\n14\n733665286\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003e\nThere are 7 palindromic substrings {\"a\", \"a,\" \"b\", \"c\", \"c\", \"d\", \"cdc\"} in the first case. For the first person, the corresponding scores are {1, 1, 1, 1, 1, 1, 27}. For the second person, the corresponding scores are {25, 25, 24, 23, 23, 22, 620}.\n\u003c/p\u003e\n"}}]}