# Problem Link:

# Difficulty:

Easy-Medium

# Pre-requisites:

Treap, Combinatorics

# Explanation:

The constraints in the first sub task are very small, so a simple brute force will be enough in order to get a nonzero score at

this problem.

In general case, let’s consider the following problem: you are given the number of each symbol’s occurences and now

you’re asked to calculate the number of different palindromes that one can obtain by permutting all these letters in some way.

Let’s consider that the i-th alphabet letter occurs **A*** times, i.e. ‘a’ occurs **A[1]** times, ‘b’ occurs **A[2]** times, and so on.

Then, we can make some observations. At first, if **A[]** contains more than one odd number (i.e. there are two letters that occurs

odd number of times), then it’s impossible to create a palindrome at all. So, in this case the answer if zero. Otherwise, if there

is one such letter, then this letter will be the “center” of the palindrome, so we place it in the center and decrease the number

of these letters. Now, **A[]** contains only even numbers. It’s a well known fact that knowing the length of the palindrome, let’s call

it **K**, and the first **(K+1)/2** letters of it, it’s trivial to reconstruct it. Also, it’s not hard to see that the number of occurrences

of each letter in the left half of a palindrome string equals to the number of occurences of each letter in the right half of a

palindrome string. Based on this, we just have to calculate the number of different ways to place **(K+1)/2** letters of 10 types

(i.e. ‘a’ to ‘i’), where the amount of letter of every type if known. It’s a well known combinatorial problem and the answer will

be **((K+1)/2)!/((A[1]/2)! * (A[2]/2)! * … * (A[10]/2)!)**. It is asked to output the result modulo a prime number, so you can use a well

known modular multiplicative inverse calculation trick in order to calculate the answer. With a proper implementation, overall

complexity of a single such a query will be O(alphabet).

So now, in the second subtask you can perform all the operations in a simple way. When you need to reverse the string, you can

do it in O(N) time. To answer the queries of another type, you can calculate the array **A[]** and then solve the problem in O(alphabet)

complexity, which is in fact very fast. So, this way we get O(M * N * alphabet) solution.

In order to pass the last sub task, you need to use some advanced data structure. Writer’s solution uses treap, which seems the

easiest way to solve the problem. The queries treap should maintain are quite standard for this structure - namely reversing the

segment and counting the number of some letter’s occurences, so it shouldn’t cause any problem.

# Setter’s solution:

Can be found here

# Tester’s solution:

Can be found here