We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- All Contests
- ProjectEuler+
- Project Euler #172: Investigating numbers with few repeated digits

# Project Euler #172: Investigating numbers with few repeated digits

# 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.