MG is a busy boy. And today he's burying himself in such a problem:
For a length of $N$, a random string made of lowercase letters, every time when it transforms, all the character $i$ will turn into $a[i]$.
MG states that the $a[i]$ consists of a permutation .
Now MG wants to know the expected steps the random string transforms to its own.
It's obvious that the expected steps $X$ will be a decimal number.
You should output $X*26^N mod $ $1000000007$.
Input
The first line is an integer $T$ which indicates the case number.($1<=T<=10$)
And as for each case, there are $1$ integer $N$ in the first line which indicate the length of random string($1<=N<=1000000000$).
Then there are $26$ lowercase letters $a[i]$ in the next line.
Output
As for each case, you need to output a single line.
It's obvious that the expected steps $X$ will be a decimal number.
You should output $X*26^N mod $ $1000000007$.
