Lucy and Palindromes

All submissions for this problem are available.
Read problems statements in Russian here
Lucy 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 lefttoright or righttoleft. For example, strings "radar" and "level" are palindromes, at the same time, strings "hello" and "world" are not.
There is a string of N latin letters. Lucy asks you to answer the following queries:
1 L R  reverse the substring from the Lth to the Rth character (1indexed), inclusive.
2 L R  calculate the number of distinct palindromes that can be obtained by permutting characters from the Lth to the Rth in the arbitrary order (ignoring all other characters of the string).
Input
The first line of input consists of two space separated integers N and M  the length of the string and the number of queries.
The second line consists of N characters from the set {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'}, describing the string. Then, M queries follow. Each query is given in one of the following forms:
1 L R  reverse the substring from the Lth to the Rth character.
2 L R  calculate the number of distinct palindromes that can be obtained by permutting characters from the Lth to the Rth in the arbitrary order, modulo 10^{9}+7 (ignoring all other characters).
Output
For every query of the type 2 output the answer on the separate line.
Example
Input: 7 4 abacaba 2 1 7 2 2 3 1 1 2 2 2 3 Output: 3 0 1
Scoring
In all the subtasks, 1 <= L <= R <= N.
Subtask 1 (33 points): 1 <= N <= 10, 1 <= M <= 1000
Subtask 2 (17 points): 1 <= N <= 1000, 1 <= M <= 1000
Subtask 3 (23 points): 1 <= N <= 4*10^{4}, 1 <= M <= 4*10^{4}
Subtask 4 (27 points): 1 <= N <= 10^{5}, 1 <= M <= 10^{5}
Time limit for subtasks 1 and 2 is 1 sec, and for the subtasks 3 and 4 it's equal to 2 sec.
Author:  xcwgf666 
Tester:  rubanenko 
Editorial  http://discuss.codechef.com/problems/PALINDR 
Tags  combinatorics, easymedium, ltime06, treap, xcwgf666 
Date Added:  14102013 
Time Limit:  1  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 