By | 18.02.2017

# WAP to Print number of not neutral numbers below 10^k mod(10^9+7)

An increasing number is a number in which values of digits increase when we go from left to right; for example,123455 . Similarly a decreasing number is a number in which values of digits decrease when we go from left to right; for example,54110 . We shall call a positive integer that is neither increasing nor decreasing a “neutral” number; for example, 151212 . As n increases, the proportion of neutral numbers below n increases such that there are 12951 numbers below one-million that are not neutral and only 277032 non-neutral numbers below 10^10.

How many numbers below 10^k are not neutral? Print the number of not neutral numbers below 10^k mod(10^9+7).

## Explanation

Input Format

First line contains an integer T which is the number of tests, next T lines contain an integer .

CONSTRAINTS

1<=T<=7

3<=k<=10

Sample Input :

3

3

5

10

Sample Output :

474

4953

277032

Time Limit:3.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 Kb

## OUTPUT : :

0 0 vote
Article Rating
Subscribe
Notify of 