# Disclaimer

This Kata is an insane step-up from [GiacomoSorbi's Kata](https://www.codewars.com/kata/total-increasing-or-decreasing-numbers-up-to-a-power-of-10/python),
so I recommend to solve it first before trying this one.

# Problem Description

A positive integer `n` is called an *increasing number* if its digits are in increasing order
(e.g. 123, 144568, 56799).

Similarly, `n` is called a *decreasing number* if its digits are in decreasing order
(e.g. 210, 76642, 998500).

Note that the numbers whose digits are all the same (e.g. 1111, 22222) are both increasing and decreasing.

Given the maximum number of digits (`max_digits`), how many positive integers in the range are either increasing or decreasing (or both)?
Since your answer will be very large, please give your answer **modulo 12345787**.

Also note that, unlike Giacomo's version, the number zero is excluded from the counts
(because it's not positive).

# Constraints

`1 <= max_digits <= 10 ** 9`

**Note the input size!**

The input will be always a valid integer.

# Examples

```python
# Up to two digits, all numbers are either increasing or decreasing
insane_inc_or_dec(1) == 9
insane_inc_or_dec(2) == 99
insane_inc_or_dec(3) == 474
insane_inc_or_dec(4) == 1674
insane_inc_or_dec(5) == 4953
insane_inc_or_dec(6) == 12951
```

# Acknowledgement

This problem was inspired by [Project Euler #113: Non-bouncy Numbers](https://projecteuler.net/problem=113).

If you enjoyed this Kata, please also have a look at [my other Katas](https://www.codewars.com/users/Bubbler/authored)!

Difficulty: interview

Starter code:

def insane_inc_or_dec(x):
	

Solutions:
from functools import reduce
from operator import mul

def insane_inc_or_dec(x):   
    return (reduce(mul,[x + i + i * (i == 10) for i in range(1, 11)]) // 3628800 - 10 * x - 2) % 12345787    

MOD = 12345787

def n_choose_k(n,k):
    if not k or n == k: return 1
    if k < 0 or k > n: return 0
    if 2*k > n: k = n - k
    ans = 1
    for i in range(k):
        ans = (ans*(n-i)//(i+1))
    return ans
    
def insane_inc_or_dec(x):
    return (n_choose_k(9+x,x) + n_choose_k(10+x,x) - 10*x - 2) % MOD


def insane_inc_or_dec(m):
    num = den = 1
    for i in range(1, 11):
        num *= m + i + i * (i >= 10)
        den *= i
    return (num // den - 10 * m - 2) % 12345787

p = 12345787

def insane_inc_or_dec(m):
    num = den = 1
    for i in range(1, 11):
        num *= m + i + i * (i == 10)
        den *= i
    return (num // den - 10 * m - 2) % p

insane_inc_or_dec = lambda Q : (reduce(lambda D,V : D * (1 + V + Q),range(9),1) * (20 + Q) / 3628800 - 10 * Q - 2) % 12345787

from functools import reduce
comb = lambda n: reduce(lambda x,y:x*y, range(n+9, n+1, -1))//40320
f = lambda n: (n**2 + 21*n + 20)*comb(n)//90 - 10*n -2
def insane_inc_or_dec(x):
    return f(x) % 12345787

import operator as op
from functools import reduce

def Combi(n, k):
    if k > n: return 0
    k1, k2 = sorted((k, n-k))
    num = reduce(op.mul, range(n, k2, -1), 1)
    d = reduce(op.mul, range(1, k1+1), 1)
    return num//d

def insane_inc_or_dec(n):
    return (Combi(n+10, 10)+Combi(n+9,9)-2-10*n)%12345787

from scipy.special import comb

MOD = 12345787

def insane_inc_or_dec(n):
    n %= MOD
    return (comb(n+10,10,exact=1) + comb(n+9,9,exact=1) - 10*n - 2) % MOD

def comb(n,k):
    c=1
    for i in range(n,n-k,-1):
        c*=i
    for i in range(1,k+1):
        c//=i
    return c

def insane_inc_or_dec(max_digits):
    increasing=comb(max_digits+9,9)-1
    decreasing=comb(max_digits+10,10)-max_digits-1
    return (increasing+decreasing-9*max_digits+1-1)%12345787

def insane_inc_or_dec(n):
    modulo = 12345787
    a, b, k = n+1, 1, 9
    for r in range(2, k+1):
        a *= n+r
        b *= r
    binomial = a//b # is (n+k)-choose-k with k=9
    return (binomial + binomial*(n+10)//10 - 10*n - 2) % modulo