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.
找到長度為 n 的數字，並且數字中不會出現指定的數字為 substring，求符合數字的總數。
特別考慮以 0 開頭的情況 (n 位數字前導不可為 0，但 n = 1 位數字可以是 0)。
最後，建造一台 AC 自動機，接著對於每一個節點著手 dp 轉移。
也就是考慮再將字串進行 AC 自動機匹配時所會遇到的所有轉移情況，因此我們要避免出現指定的字符串時，在結尾處標記不可轉移即可。