#include #include #include using namespace std; using i64 = int64_t; constexpr int mod = static_cast(powl(10, 9)) + 7; i64 f(string s) { int n = static_cast(s.size()); // dp[未満フラグ][先行ゼロでないか][前の数字] := パターン数 vector>> dp(2, vector>(2, vector(10, 0))); dp[0][0][0] = 1; for(int i=0; i>> ndp(2, vector>(2, vector(10, 0))); for(int less=0; less<2; ++less) { for(int nuke0=0; nuke0<2; ++nuke0) { for(int before=0; before<10; ++before) { if(!dp[less][nuke0][before]) { continue; } int start = nuke0 ? before : 0; for(int d=start; d<=(less ? 9 : s[i]-'0'); ++d) { int nless = less || d < s[i] - '0', n_nuke0 = nuke0 || d > 0, nbefore = d; ndp[nless][n_nuke0][nbefore] += dp[less][nuke0][before]; ndp[nless][n_nuke0][nbefore] %= mod; } } } } dp = ndp; } i64 res = 0; for(int less=0; less<2; ++less) { for(int nuke0=0; nuke0<2; ++nuke0) { for(int before=0; before<10; ++before) { res += dp[less][nuke0][before]; res %= mod; } } } return res; } int main(void) { int n; scanf("%d", &n); string s = ""; for(int i=0; i