Description
I'm a salary thief who don't answer students' question
~by anonymous TA
"I sucked!" TA think he's the worst, therefore he only asks you to do some cut and paste.
You got a string and your cursor is at the leftmost position of the string.
Let's call the leftmost position of the string position 0.
The string only contains character '1'~'3'.
You need to move the cursor to the right x times.
Each time only cross one character.
After the move, you divide the string into two part.
You cut the right part, and paste it for n times.
For n = the last character of left part of the string.
You need to answer how long the string is after x moves.
Because the string may be very long, you only need to answer the length of the final string mod 10^9+7(output positive number)
We guarantee that each move will not on empty character​.
Example:
Given x = 5, string = "231"
Move 1(position 0->1):
cut the string "231" -> "2" and "31"
the last character of left part of the string = "2"
past "31" for 2 times, we got "23131"
Move 2(position 1->2):
cut the string "23131" -> "23" and "131"
the last character of left part of the string = "3"
past "131" for 3 times, we got "23131131131"
Move 3(position 2->3):
cut the string "23131131131" -> "231" and "31131131"
the last character of left part of the string = "1"
past "31131131" for 1 times, we got "23131131131"
Move 4(position 3->4):
cut the string "23131131131" -> "2313" and "1131131"
the last character of left part of the string = "3"
past "1131131" for 3 times, we got "2313113113111311311131131"
Move 5(position 4->5):
cut the string "2313113113111311311131131" -> "23131" and "13113111311311131131"
the last character of left part of the string = "1"
past "13113111311311131131" for 1 times, we got "2313113113111311311131131"
The final string "2313113113111311311131131" has length 25.
The answer will be 25%(10^9+7) = 25
Input
First line contains one integer t(1 <= t <= 10) which means the number of testcases.
Each testcase contains two lines.
First line contains one integer x(1 <= x <= 10^6)
Second line contains a string. ( 1 <= length of the string <= 500)
Output
For each testcase, print only one positive number which means the length of the final string mod 10^9+7
Remember to print \n at the end of output.