#include using namespace std; #define rep(i,n) for(int i=0,_i=(n);i<_i;++i) template struct MInt { long long val; constexpr MInt(long long val = 0) : val(val % MOD) { if (val < 0) val += MOD; } MInt operator+(const MInt& n) const { return MInt(val) += n; } MInt operator-(const MInt& n) const { return MInt(val) -= n; } MInt& operator+=(const MInt& n) { val = (val + n.val) % MOD; return *this; } MInt& operator-=(const MInt& n) { val = (MOD + val - n.val) % MOD; return *this; } friend ostream& operator<<(ostream& os, const MInt& n) { os<; constexpr int MAX_N = 1e6; bool visited[MAX_N+1][10]; mint dp[MAX_N+1][10]; mint dfs(int n, int t) { // 10^n未満で、直前の桁の数がtであるときのAscNumberの個数 if (n == 1) return 10-t; if (visited[n][t]) return dp[n][t]; mint ans = 0; rep(i, 10-t) { ans += dfs(n-1, t+i); } visited[n][t] = true; return dp[n][t] = ans; } int main() { int N; cin >> N; cout << dfs(N, 0) << endl; return 0; }