S.H.I.E.L.D. uses a cryptographic scheme to transmit messages securely. The scheme maps words with positive integers as follows - 'a' is mapped with 1, 'b' with 2, ...., 'z' with 26, 'aa' with 27, 'ab' with 28, ..., 'zz' with 676 and so on. Thus, each positive integer is mapped with a distinct lower case word.

When sending a message, the encrypted words are separated with commas. Furthermore, the system occasionally adds zero or more leading zeros to the individual words. For example, 217,9,39 and 217,09,00000039 are both valid encodings of the message "hi i am".

Hawk-eye, while sending a message forgot to include commas between different words and instead sent a continuous stream of digits. On the receiving end, Colonel Fury got the message as a sequence of digits. You need to find the number of possible messages that could have resulted in the received cipher.

Help Colonel Fury find total number of possible valid messages that could have resulted in this encryption. Because this number may be quite large, output the result modulo 10⁹+7.

Input:

First line of the input contains T (1<=T<=100), the number of test cases. For each test case, the first line contains a positive integer N (1<=N<=2000), denoting the number of digits in the received cipher. The second line contains the ciper-text of length N.

Output:

Output T lines with each line containing the number of possible messages modulo 1000000007.