# 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)!

Source: codewars | Difficulty: MEDIUM
Tags: Mathematics

Ad-hoc

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


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
	return (binomial + binomial * (n + 10) // 10 - 10 * n - 2) % modulo