ABC 029

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string N;
    cin >> N;

    int sz = N.size();

    int mx = 15;
    vector dp(sz + 1, vector(2, vll(mx)));
    dp[0][0][0] = 1;

    rep2(i, 1, sz + 1) {
        int t = N[i - 1] - '0';
        rep(d, 10) {
            bool is_one = d == 1;
            rep(c, mx) {
                if (d < t) {
                    dp[i][1][c + is_one] += dp[i - 1][0][c];
                }
                if (d == t) {
                    dp[i][0][c + is_one] += dp[i - 1][0][c];
                }
                dp[i][1][c + is_one] += dp[i - 1][1][c];
            }
        }
    }

    ll ans = 0;
    rep2(c, 1, mx) {  // (N 未満の数で 1 の個数が c 個である数の個数) * c
        ans += dp[sz][1][c] * c;
    }
    for (char c : N) {  // N そのものの 1 の個数を数える
        if (c == '1') ans++;
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string S;
    cin >> S;

    ll N = S.size();

    int ndigit = 15;

    // dp[is_less][# of 1]
    vector dp(2, vll(ndigit));
    dp[0][0] = 1;

    rep(i, N) {
        int t = S[i] - '0';
        vector dpn(2, vll(ndigit));

        rep(d, 10) rep(is_less, 2) rep(num, ndigit) {
            if (!is_less && d > t) continue;
            int is_less_n = is_less || d < t;
            int add = d == 1;

            dpn[is_less_n][num + add] += dp[is_less][num];
        }

        swap(dp, dpn);
    }

    ll ans = 0;
    rep(num, ndigit) rep(is_less, 2) {
        ans += dp[is_less][num] * num;
    }

    cout << ans << endl;
}