{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in Russian \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME06/russian/PALINDR.pdf\"\u003ehere\u003c/a\u003e\u003c/h3\u003e\r\n\u003cp\u003eLucy had recently learnt about palindromes. As you may probably know, palindrome is a string that reads the same way in the both directions, that is left-to-right or right-to-left. For example, strings \"radar\" and \"level\" are palindromes, at the same time, strings \"hello\" and \"world\" are not.\u003c/p\u003e\r\n\r\n\u003cp\u003eThere is a string of \u003cb\u003eN\u003c/b\u003e latin letters. Lucy asks you to answer the following queries:\u003cbr\u003e\r\n1 \u003cb\u003eL\u003c/b\u003e \u003cb\u003eR\u003c/b\u003e - reverse the substring from the \u003cb\u003eL\u003c/b\u003e-th to the \u003cb\u003eR\u003c/b\u003e-th character (1-indexed), inclusive.\u003cbr\u003e\r\n2 \u003cb\u003eL\u003c/b\u003e \u003cb\u003eR\u003c/b\u003e - calculate the number of distinct palindromes that can be obtained by permutting characters from the \u003cb\u003eL\u003c/b\u003e-th to the \u003cb\u003eR\u003c/b\u003e-th in the arbitrary order (ignoring all other characters of the string).\u003cbr\u003e\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\nThe first line of input consists of two space separated integers \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eM\u003c/b\u003e - the length of the string and the number of queries.\r\nThe second line consists of \u003cb\u003eN\u003c/b\u003e characters from the set {\u0027\u003cb\u003ea\u003c/b\u003e\u0027, \u0027\u003cb\u003eb\u003c/b\u003e\u0027, \u0027\u003cb\u003ec\u003c/b\u003e\u0027, \u0027\u003cb\u003ed\u003c/b\u003e\u0027, \u0027\u003cb\u003ee\u003c/b\u003e\u0027, \u0027\u003cb\u003ef\u003c/b\u003e\u0027, \u0027\u003cb\u003eg\u003c/b\u003e\u0027, \u0027\u003cb\u003eh\u003c/b\u003e\u0027, \u0027\u003cb\u003ei\u003c/b\u003e\u0027, \u0027\u003cb\u003ej\u003c/b\u003e\u0027}, describing the string. Then, \u003cb\u003eM\u003c/b\u003e queries follow. Each query is given in one of the following forms:\u003cbr\u003e\r\n1 \u003cb\u003eL\u003c/b\u003e \u003cb\u003eR\u003c/b\u003e - reverse the substring from the \u003cb\u003eL\u003c/b\u003e-th to the \u003cb\u003eR\u003c/b\u003e-th character.\u003cbr\u003e\r\n2 \u003cb\u003eL\u003c/b\u003e \u003cb\u003eR\u003c/b\u003e - calculate the number of distinct palindromes that can be obtained by permutting characters from the \u003cb\u003eL\u003c/b\u003e-th to the \u003cb\u003eR\u003c/b\u003e-th in the arbitrary order, modulo \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e+7\u003c/b\u003e (ignoring all other characters).\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor every query of the type \u003cb\u003e2\u003c/b\u003e output the answer on the separate line.\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n7 4\r\nabacaba\r\n2 1 7\r\n2 2 3\r\n1 1 2\r\n2 2 3\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n3\r\n0\r\n1\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003eScoring\u003c/h3\u003e\r\nIn all the subtasks, 1 \u003c\u003d \u003cb\u003eL\u003c/b\u003e \u003c\u003d \u003cb\u003eR\u003c/b\u003e \u003c\u003d \u003cb\u003eN\u003c/b\u003e.\u003cbr\u003e\r\nSubtask 1 (33 points): 1 \u003c\u003d \u003cb\u003eN\u003c/b\u003e \u003c\u003d 10, 1 \u003c\u003d \u003cb\u003eM\u003c/b\u003e \u003c\u003d 1000\u003cbr\u003e\r\nSubtask 2 (17 points): 1 \u003c\u003d \u003cb\u003eN\u003c/b\u003e \u003c\u003d 1000, 1 \u003c\u003d \u003cb\u003eM\u003c/b\u003e \u003c\u003d 1000\u003cbr\u003e\r\nSubtask 3 (23 points): 1 \u003c\u003d \u003cb\u003eN\u003c/b\u003e \u003c\u003d 4*10\u003csup\u003e4\u003c/sup\u003e, 1 \u003c\u003d \u003cb\u003eM\u003c/b\u003e \u003c\u003d 4*10\u003csup\u003e4\u003c/sup\u003e\u003cbr\u003e\r\nSubtask 4 (27 points): 1 \u003c\u003d \u003cb\u003eN\u003c/b\u003e \u003c\u003d 10\u003csup\u003e5\u003c/sup\u003e, 1 \u003c\u003d \u003cb\u003eM\u003c/b\u003e \u003c\u003d 10\u003csup\u003e5\u003c/sup\u003e\u003cbr\u003e\r\nTime limit for subtasks 1 and 2 is 1 sec, and for the subtasks 3 and 4 it\u0027s equal to 2 sec."}}]}