{"raw_statement":[{"iden":"statement","content":"In a restaurant, given N menus, where the menus are represented by the strings S1, ..., SN. Each string Si is associated with an array Ai (of the same length) of joy levels. In this problem, you should choose a submenu defined by three integers (i, j, k), where i is the index of one of the menus, and j, k specify a substring of this chosen menu.\n\nWe need to find the submenu of the highest quality, where the quality Q is defined by the function: \n\nCan you find the submenu of the highest quality? Please output the corresponding highest quality of the function Q.\n\nThe first line of the input contains a single integer T specifying the number of test cases.\n\nEach test case begins with a line containing an integer N (1 ≤ N ≤ 105) specifying the number of menus in the restaurant.\n\nThen N lines follow, the ith line contains a string Si representing the ith menu. All the menus are non-empty strings consisting of lowercase English letters, and the sum of their lengths will not exceed 105 per test case.\n\nThen N lines follow, the ith line contains array Ai, in which Ai has the same length as string Si and (0 ≤ Aik ≤ 109). The values of each array are space-separated.\n\nFor each test case, print a single line containing an integer Q representing the maximum quality corresponding to the best submenu (i, j, k).\n\nThe triples corresponding to the answers of the two given cases are (1, 1, 5) and (1, 4, 5).\n\n"},{"iden":"input","content":"The first line of the input contains a single integer T specifying the number of test cases.Each test case begins with a line containing an integer N (1 ≤ N ≤ 105) specifying the number of menus in the restaurant.Then N lines follow, the ith line contains a string Si representing the ith menu. All the menus are non-empty strings consisting of lowercase English letters, and the sum of their lengths will not exceed 105 per test case.Then N lines follow, the ith line contains array Ai, in which Ai has the same length as string Si and (0 ≤ Aik ≤ 109). The values of each array are space-separated."},{"iden":"output","content":"For each test case, print a single line containing an integer Q representing the maximum quality corresponding to the best submenu (i, j, k)."},{"iden":"note","content":"The triples corresponding to the answers of the two given cases are (1, 1, 5) and (1, 4, 5)."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ N_k, K_k \\in \\mathbb{Z} $ satisfy $ 1 \\leq K_k \\leq N_k \\leq 200 $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unknown (but input-limited)} $  \n2. For each test case: $ 1 \\leq K_k \\leq N_k \\leq 200 $  \n\n**Objective**  \nFor each test case $ k $, compute the number of permutations $ \\pi \\in S_{N_k} $ such that the maximum length of a contiguous increasing subarray in $ \\pi $ is exactly $ K_k $.  \nOutput the result modulo $ 10^9 + 7 $.","simple_statement":"Count permutations of length N where the longest increasing contiguous subarray has exactly length K.  \nAnswer modulo 10^9+7.","has_page_source":false}