#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(10, 0)); dp[0][0] = 1; for(int i=0; i> ndp(2, vector(10, 0)); for(int less=0; less<2; ++less) { for(int before=0; before<10; ++before) { if(!dp[less][before]) { continue; } for(int d=before; d<=(less ? 9 : s[i]-'0'); ++d) { int nless = less || d < s[i] - '0', nbefore = d; ndp[nless][nbefore] += dp[less][before]; ndp[nless][nbefore] %= mod; } } } dp = ndp; } i64 res = 0; for(int less=0; less<2; ++less) { for(int before=0; before<10; ++before) { res += dp[less][before]; res %= mod; } } return res; } int main(void) { int n; scanf("%d", &n); string s = ""; for(int i=0; i