{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n \"HTML-CSS\": {\n preferredFont: \"TeX\",\n availableFonts: [\"STIX\",\"TeX\"],\n linebreaks: { automatic:true },\n EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)\n },\n ShowMathMenu: false,\n TeX: {\n extensions: [\"color.js\"],\n noUndefined: {\n attributes: {\n mathcolor: \"red\",\n mathbackground: \"#FFEEEE\",\n mathsize: \"90%\"\n }\n },\n Macros: { href: \"{}\" }\n },\n tex2jax: {\n inlineMath: [[\u0027$\u0027,\u0027$\u0027], [\u0027\\\\(\u0027,\u0027\\\\)\u0027]],\n displayMath: [ [\"$$\",\"$$\"], [\"\\\\[\", \"\\\\]\"] ],\n multiline: true,\n processEscapes: true\n },\n menuSettings: {\n context: \"Browser\"\n },\n messageStyle: \"none\"\n });\n \u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\u003c/script\u003e\n\u003cp\u003eЛюси недавно узнала о палиндромах. Как вы наверняка знаете, палиндром - это строка, которая одинаково читается слева направо и справа налево. К примеру, строки \"radar\" и \"level\" - палиндромы, но в то же время строки \"hello\" и \"world\" не являются палиндромами.\u003c/p\u003e\n\n\u003cp\u003eДана строка из \u003cb\u003eN\u003c/b\u003e английских букв. Люси просит вас ответить на следующие запросы:\u003cbr\u003e\n1 \u003cb\u003eL\u003c/b\u003e \u003cb\u003eR\u003c/b\u003e - развернуть подстроку с \u003cb\u003eL\u003c/b\u003e-ого по \u003cb\u003eR\u003c/b\u003e-ый символ включительно в 1-индексации.\u003cbr\u003e\n2 \u003cb\u003eL\u003c/b\u003e \u003cb\u003eR\u003c/b\u003e - посчитать количество различных палиндромов, которые можно получить перестановкой символов на отрезке с \u003cb\u003eL\u003c/b\u003e-ого по \u003cb\u003eR\u003c/b\u003e-ый в произвольном порядке (игнорируя все остальные символы строки).\u003cbr\u003e\u003c/p\u003e\n\n\u003ch3\u003eВходные данные\u003c/h3\u003e\nПервая строка ввода содержит два разделённых пробелом целых числа \u003cb\u003eN\u003c/b\u003e и \u003cb\u003eM\u003c/b\u003e (1\u003c\u003d N, M \u003c\u003d 10^5) - длину строки и количество запросов.\nВо второй строке записаны \u003cb\u003eN\u003c/b\u003e символов из множества {\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}, описывающих строку. Затем следуют M запросов. Каждый запрос описан одним из следующих способов:\u003cbr\u003e\n1 \u003cb\u003eL\u003c/b\u003e \u003cb\u003eR\u003c/b\u003e - развернуть подстроку с \u003cb\u003eL\u003c/b\u003e-ого по \u003cb\u003eR\u003c/b\u003e-ый символ.\u003cbr\u003e\n2 \u003cb\u003eL\u003c/b\u003e \u003cb\u003eR\u003c/b\u003e - вычислить количество различных палиндромов, которые можно получить перестановкой символов с \u003cb\u003eL\u003c/b\u003e-го по \u003cb\u003eR\u003c/b\u003e-ый в произвольном порядке, по модулю \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e+7\u003c/b\u003e (игнорируя все остальные символы строки).\n\n\u003ch3\u003eВыходные данные\u003c/h3\u003e\n\u003cp\u003eДля каждого запроса типа \u003cb\u003e2\u003c/b\u003e выведите ответ на отдельной строке.\u003c/p\u003e\n\n\u003ch3\u003eПример\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n7 4\nabacaba\n2 1 7\n2 2 3\n1 1 2\n2 2 3\n\n\u003cb\u003eOutput:\u003c/b\u003e\n3\n0\n1\n\u003c/pre\u003e"}}]}