G. Special Bracelets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

To celebrate their first anniversary together, Alan and Tafnes will make two bracelets as a present to remember each other in the distance. They bought $$$m+n$$$ beads, each with a lowercase letter written in them. Alan will take any $$$m$$$ beads to make his bracelet (let's call it $$$B_A$$$) and Tafnes will take the remaining $$$n$$$ beads to make her bracelet (let's call it $$$B_T$$$). Since this couple is very weird and wonderful, $$$m$$$ and $$$n$$$ will always be prime numbers.

A bracelet is a circular arrangement of strung beads equally spaced which can be represented as a string. Let $$$C$$$ and $$$D$$$ be bracelets, we consider that $$$C \neq D$$$ if bracelet $$$C$$$ cannot be obtained from bracelet $$$D$$$ by rotating it by any angle.

So, Alan an Tafnes are now wondering: how many distinct pairs of bracelets $$$(B_A, B_T)$$$ can they obtain? The beads in each bracelet can be strung in any order they want, and the pair $$$(B_A, B_T)$$$ is to be considered distinct from the pair $$$(B_T, B_A)$$$ unless $$$B_A=B_T$$$.

Input

The first line contains two prime positive integers $$$m$$$ and $$$n$$$ ($$$2 \leq m, n \leq 18002$$$, $$$m+n \leq 18002$$$) — the number of beads they bought.

The second line contains a string of length $$$m+n$$$ consisting only of lowercase English letters — the beads they bought.

Output

Print a single integer — the number of distinct pairs of bracelets $$$(B_A, B_T)$$$. Since this number can be very large, print it modulo the prime number $$$515011997$$$.

Examples
Input
2 2
abcd
Output
6
Input
3 7
aabeinottt
Output
14640
Note

In the first example, they can obtain the following six pairs of bracelets: $$$(ab, cd)$$$, $$$(ac, bd)$$$, $$$(ad, bc)$$$, $$$(bc, ad)$$$, $$$(bd, ac)$$$ and $$$(cd, ab)$$$. For example, note that the pair $$$(ca, bd)$$$ is the same as $$$(ac, bd)$$$ because $$$ca$$$ is a rotation of $$$ac$$$.