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

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

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

 

Leave a Reply