{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e\nFor the given string \u003cb\u003eS\u003c/b\u003e of length \u003cb\u003eN\u003c/b\u003e you need to find for each \u003cb\u003eL\u003c/b\u003e from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e the first non-palindrome substring of \u003cb\u003eS\u003c/b\u003e that has length \u003cb\u003eL\u003c/b\u003e. That is, for each \u003cb\u003eL\u003c/b\u003e from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e you need to find the smallest positive integer \u003cb\u003eK \u003c\u003d N - L + 1\u003c/b\u003e such that the string \u003cb\u003eS[K, K + L - 1]\u003c/b\u003e is not a palindrome. Denote this number by \u003cb\u003eK(L)\u003c/b\u003e. Here \u003cb\u003eS[i, j]\u003c/b\u003e stands for the substring of \u003cb\u003eS\u003c/b\u003e composed of its characters in positions \u003cb\u003ei, i + 1, ..., j\u003c/b\u003e. Characters of \u003cb\u003eS\u003c/b\u003e are numbered from \u003cb\u003e1\u003c/b\u003e to \u003cb\u003eN\u003c/b\u003e. If for some \u003cb\u003eL\u003c/b\u003e there is no such \u003cb\u003eK\u003c/b\u003e set \u003cb\u003eK(L) \u003d 0\u003c/b\u003e. After you find all numbers \u003cb\u003eK(1), K(2), ..., K(N)\u003c/b\u003e output the following sum\u003cbr /\u003e\n\u003cbr /\u003e\u003ccenter\u003e\u003cbr /\u003e\n\u003cb\u003e100007\u003csup\u003eN - 1\u003c/sup\u003e * K(1) + 100007\u003csup\u003eN - 2\u003c/sup\u003e * K(2) + ... + 100007 * K(N - 1) + K(N)\u003c/b\u003e\u003cbr /\u003e\n\u003c/center\u003e\u003cbr /\u003e\n\u003cbr /\u003e\u003cbr /\u003e\nmodulo \u003cb\u003e2\u003csup\u003e64\u003c/sup\u003e\u003c/b\u003e.\u003cbr /\u003e\n\u003cbr /\u003e\u003cbr /\u003e\u003cbr /\u003e\n\u003cb\u003eRemark.\u003c/b\u003e The string is called a palindrome if it coincides with its reverse. So \u003cb\u003eabacaba\u003c/b\u003e and \u003cb\u003eabba\u003c/b\u003e are palindromes but \u003cb\u003ecodechef\u003c/b\u003e and \u003cb\u003eabbc\u003c/b\u003e are not.\u003c/p\u003e\n\u003cp\u003e\u003ch3\u003eInput\u003c/h3\u003e\n\u003c/p\u003e\u003cp\u003e The first line contains a single integer \u003cb\u003eT\u003c/b\u003e, the number of test cases. \u003cb\u003eT\u003c/b\u003e test cases follow. The only line of each test case contains a non-empty string composed only of lowercase letters of the English alphabet.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e For each test case, output a single line containing the corresponding sum constructed by numbers \u003cb\u003eK(1), K(2), ..., K(N)\u003c/b\u003e as mentioned in the problem statement modulo \u003cb\u003e2\u003csup\u003e64\u003c/sup\u003e\u003c/b\u003e.\u003c/p\u003e\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003e\u003cbr /\u003e\n1 \u003c\u003d T \u003c\u003d 20\u003cbr /\u003e\n\u003cbr /\u003e\u003cbr /\u003e\n1 \u003c\u003d length of S \u003c\u003d 100000\u003cbr /\u003e\n\u003c/b\u003e\u003c/p\u003e\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\n\u003cb\u003eInput:\u003c/b\u003e\n4\nabacaba\nabba\ncodechef\naaaa\n\n\u003cb\u003eOutput:\u003c/b\u003e\n12789123637940213592\n10001500056\n18134494634143926857\n0\n\u003c/pre\u003e\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003eActual values of \u003cb\u003eK(1), K(2), ..., K(N)\u003c/b\u003e in the tests are:\u003cbr /\u003e\n\u003cbr /\u003eabacaba: {0, 1, 2, 1, 1, 1, 0}\u003cbr /\u003e\n\u003cbr /\u003eabba: {0, 1, 1, 0}\u003cbr /\u003e\n\u003cbr /\u003ecodechef: {0, 1, 1, 1, 1, 1, 1, 1}\u003cbr /\u003e\n\u003cbr /\u003eaaaa: {0, 0, 0, 0}\u003c/p\u003e\n"}}]}