This problem is a programming version of Problem 172 from projecteuler.net
How many positive -digit numbers (without leading zeroes) are there such that no digit occurs more than times in ? Output the answer modulo .
Input Format
The first line of input contains two integers and . Here, is the number of queries. The following lines contain an integer each.
Constraints
Output Format
For each query, print the integer which is the answer to the problem modulo .
Sample Input 0
3 2
3
4
Sample Output 0
900
8991
Explanation 0
For the first query, each -digit number is valid. For the second query, each -digit number except for , , , , , , , , and is valid.