F. John and Computer Science
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

John is in the middle of his Operating Systems exam and he just realized that he forgot a command that he needs. To save his grade he decided to randomly type letters in the hopes that he will get some partial score for trying.

The teacher knows the command that John needs for his program to run, so he wonders what is expected number of key strokes after which the necessary comand will be a suffix of the written text.

The expected value can be written in the form $$$\frac{p}{q} $$$. Please output $$$p \cdot q^{-1} \pmod{1000000007} $$$, where $$$q^{-1}$$$ is the modular inverse of $$$q$$$.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 1000)$$$, the size of the command.

The second line contains a string consisting of $$$n$$$ lower case characters, the searched for command. The command only consists of lower case letters from the standard english alphabet.

Output

Output a single integer, the requested number modulo $$$10^9 + 7$$$.

Examples
Input
1
a
Output
26
Input
2
aa
Output
702
Input
5
tbddu
Output
11881376