from collections.abc import Iterable def accum_dp(xs: Iterable, f, op, e, init: dict, *, is_reset=True): dp = init.copy() for x in xs: pp = {} if is_reset else dp.copy() dp, pp = pp, dp for fm_key, fm_val in pp.items(): for to_key, to_val in f(fm_key, fm_val, x): dp[to_key] = op(dp.get(to_key, e), to_val) return dp def f(k, v, x): lz, last, lt = k # (leading zero, 末尾の数字, 未満か) if lz: for d in range(1, 10): yield (False, d, True), 1 yield (True, 0, True), 1 # leading zero 維持 else: for d in range(last, 10): if not lt and d > x: break nlt = lt | (d < x) yield (False, d, nlt), v def op(a, b): return (a + b) % MOD def digit_dp() -> int: digits = [9] * N init = {(True, 0, True): 1} for d in range(1, digits[0]+1): lz = False last = d lt = d < digits[0] init[lz, last, lt] = 1 dp = accum_dp(digits[1:], f, op, 0, init) res = 0 for (lz, _, _), v in dp.items(): if lz: continue res += v res %= MOD return res + 1 # +1 はゼロの分 MOD = 10**9 + 7 N = int(input()) ans = digit_dp() print(ans)