この問題は、いわゆる桁 DP を使って解くことができます。

桁 DP とは、整数を（例えば十進表記の）文字列と捉え、一桁ずつ桁を追加することに対応する状態遷移によって条件を満たす整数全体に対して DP を行う手法です。 特に、「\(N\) 以下の整数」を管理するために「すでに \(N\) 以下になることが確定しているか」のフラグを用いるものを指して桁 DP と呼ぶことも多いです。

この問題では、一般的な「\(N\) 以下の整数全体」に対して処理を行う桁 DP に加えて、次のような情報を状態として持てばよいです。

• 桁に \(0\) が含まれるか
• 直前に追加した桁は何か

実装例は以下のようになります。 以下の実装例ではメモ化再帰を使って桁 DP を行っています。

#include <iostream>
#include <map>
#include <atcoder/modint>
using namespace std;
using modint = atcoder::static_modint<1000000007>;

int main() {
    long N;
    cin >> N;

    struct dp_value { // DP の値
        modint count; // 条件を満たす整数の個数 (桁に 0 を含むものは 2 回数える)
        modint score_sum; // 条件を満たす整数のスコアの総和

        dp_value& operator+=(const dp_value& rhs) {
            count += rhs.count;
            score_sum += rhs.score_sum;
            return *this;
        }

        dp_value add(const modint& mint) {
            return {count, score_sum + mint * count};
        }
    };
    map<tuple<long, long, bool, int, bool>, dp_value> memo;
    cout << [&memo](this auto rec, long coef, long upper, bool is_zero, int prev, bool has_zero) -> dp_value {
        if (upper == 0) // 区間が空なら
            return dp_value{0, 0}; // 0 個
        if (coef == 0) { // 一の位まで見終えたら
            if (is_zero) // 0 なら
                return dp_value{0, 0}; // 0 個
            return dp_value{1 + has_zero}; // そうでなければ 1 個 + 桁に 0 を含めばさらに 1 個
        }

        if (memo.contains({coef, upper, is_zero, prev, has_zero}))
            return memo[{coef, upper, is_zero, prev, has_zero}];
        dp_value ret{};
        for (int i = 0; i < 10; ++i) {
            long next_upper = clamp(upper - i * coef, 0L, coef);
            if (!is_zero)
                ret += rec(coef / 10, next_upper, false, i, has_zero || i == 0).add(max(prev, i) - min(prev, i));
            else if (i == 0)
                ret += rec(coef / 10, next_upper, true, 0, false);
            else
                ret += rec(coef / 10, next_upper, false, i, i == 0);
        }
        return memo[{coef, upper, is_zero, prev, has_zero}] = ret;
    }(1000000000000000000, N + 1, true, 0, false).score_sum.val() << endl;
    return 0;
}