Nhìn vào bài toán, ta có thể nghĩ ngay tới quy hoạch động chữ số, một trong những thuật toán quy hoạch động cổ điển. Tuy nhiên, vì giới hạn ~n~ tương đối lớn, ta cần tìm cách tối ưu hơn.

Nhận xét quan trọng: Ta thấy được, nếu ~(n\ mod\ 10^{11})~ chia hết cho ~2048~ (hay nói cách khác, ~11~ chữ số cuối cùng của ~n~ chia hết cho ~2048~) thì ~n~ cũng chia hết cho ~2048~ (chứng minh dễ, xin nhường lại cho bạn đọc).

Vì vậy, ta chỉ cần quy hoạch động trên ~11~ chữ số cuối cùng của ~n~, còn các ký tự ~\texttt{?}~ ngoài ~11~ ký tự cuối có thể điền chữ số bất kỳ.

Độ phức tạp: ~O((n - 11) + 11 \cdot 2048)~ = ~O(n)~.

Code mẫu

#include <bits/stdc++.h>

using namespace std;
#define DB(X) { cout << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cout << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cout << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cout << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cout << '\n'; for (int _ = l; _ <= r; ++_) DB1(A, _); cout << '\n';}
#define sz(x) ((int) (x).size())
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
const int mod = 1 << 11, MOD = 1e9 + 9;
vector<int> pos;
int mem[13][2048];
int dp(int p, int sum) {
    if (p == sz(pos)) {
        return sum == 0;
    }
    int &res = mem[p][sum];
    if (res != -1) {
        return res;
    }
    res = 0;
    for (int i = 0; i <= 9; ++i) {
        int nsum = (sum + pos[p] * i) % mod;
        res = (res + dp(p + 1, nsum)) % MOD;
    }
    return res;
}
int32_t main() {
#ifdef HynDuf
    freopen("A.inp", "r", stdin);
    freopen("A.out", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    string s;
    cin >> s;
    reverse(all(s));
    int pw10 = 1, cur = 0, ans = 1;
    for (int i = 0; i < sz(s); ++i) {
        char c = s[i];
        if (c != '?') {
            if (i <= 10) {
                cur = (cur + (c - '0') * pw10) % mod;
            }
        } else {
            if (i > 10) {
                ans = ans * 10LL % MOD;
            } else {
                pos.push_back(pw10);
            }
        }
        pw10 = pw10 * 10 % mod;
    }
    memset(mem, -1, sizeof(mem));
    cout << ans * 1LL * dp(0, cur) % MOD;
}