Some people believe that 13 is an unlucky number. So they always want to avoid the number 13. But I believe that 7 is an unlucky number and want to avoid it. So unlucky number is different for man to man. If 13 is an unlucky number and in a number there is no 13 (i.e. no '1' is followed by a '3') then we can call it a lucky number. For example, if we consider 13 as an unlucky number then 12345 is a lucky number. But if any number contains 13 then it is not a lucky number, such as 13254 and 21345 are not lucky numbers. Given the number of digits N in a number and the unlucky number M, you have to find out how many lucky numbers are possible with N digits considering that M is unlucky number. Note that leading 0's are not allowed. So, 011 is not a valid three digit number.
The first line of the input file contains an integer T (T ≤ 1000) which denotes the total number of test cases.
The description of each test case is given below:
Two positive integers N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 10100).
For each test case print the number of lucky numbers of N digits considering that M is the unlucky number. The result may be very large. You have to output the result modulo 10000007.
3 1 3 2 13 2 1
9 89 72