Project Euler #172: Investigating numbers with few repeated digits

_{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.