MG loves string

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

Description

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$.

Sample Input

2 2 abcdefghijklmnpqrstuvwxyzo 1 abcdefghijklmnopqrstuvwxyz

Sample Output

5956 26

Hint

wange2014

Source

BestCoder Round #93

提交代码