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 . Python is an high-level language 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

## SOURCE CODE ::

```import math
def binomial(n, k):
assert 0 <= k <= n
return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
def compute(a):
DIGITS = a
increasing = binomial(DIGITS + 9, 9) - 1
decreasing = binomial(DIGITS + 10, 10) - (DIGITS + 1)
flat = DIGITS * 9
ans = (increasing + decreasing - flat)
return str(ans)
a=input()
for i in range(0,a,1):
print(compute(input()))```

## OUTPUT : :

```//First Run---------------------------------------------------

3

3
474

5
4953

10
277032

//Second Run---------------------------------------------

3

4
1674

20
40059818

100
51161058134250```

Article Rating
Category: Tricky Q Tags:  