def getMinErrors(errorString, x, y):
    MOD = 10**9 + 7
    n = len(errorString)
    pre0 = [0] * (n + 1)  # prefix count of 0s
    pre1 = [0] * (n + 1)  # prefix count of 1s
    preq = [0] * (n + 1)  # prefix count of wildcards
 
    # Build prefix sums
    for i in range(n):
        pre0[i+1] = pre0[i] + (1 if errorString[i] == '0' else 0)
        pre1[i+1] = pre1[i] + (1 if errorString[i] == '1' else 0)
        preq[i+1] = preq[i] + (1 if errorString[i] == '!' else 0)
 
    suf0 = [0] * (n + 1)
    suf1 = [0] * (n + 1)
    sufq = [0] * (n + 1)
    for i in reversed(range(n)):
        suf0[i] = suf0[i+1] + (1 if errorString[i] == '0' else 0)
        suf1[i] = suf1[i+1] + (1 if errorString[i] == '1' else 0)
        sufq[i] = sufq[i+1] + (1 if errorString[i] == '!' else 0)
 
    # Count total number of wildcards
    total_q = preq[n]
 
    # Try all possible cuts: wildcards before i are '0', after i are '1'
    # And also wildcards before i are '1', after i are '0'
    min_err = float('inf')
 
    # Prepare for cut: all wildcards as '0' or as '1'
    def count_errors(a, b):
        # Count number of 01 and 10 subsequences
        cnt0 = cnt1 = cntq = 0
        cnt_01 = cnt_10 = 0
        for c in errorString:
            if c == '0':
                cnt0 += 1
                cnt_10 += cnt1
            elif c == '1':
                cnt1 += 1
                cnt_01 += cnt0
            else:
                cnt0 += a
                cnt1 += b
                cnt_10 += cnt1 * a
                cnt_01 += cnt0 * b
        return cnt_01 * x + cnt_10 * y
 
    # Try all wildcards as '0'
    err0 = count_errors(1, 0)
    # Try all wildcards as '1'
    err1 = count_errors(0, 1)
    min_err = min(err0, err1)
 
    # Now try for all possible cuts
    # Precompute: for each i, how many wildcards up to i are assigned '0', after are '1'
    pre_q0 = 0
    for cut in range(n + 1):
        zeros = pre0[cut] + preq[cut]  # 0s and ! assigned 0 to the left
        ones = suf1[cut] + sufq[cut]   # 1s and ! assigned 1 to the right
        # Number of 01 subsequences: number of 0s left * number of 1s right
        num_01 = zeros * ones
        # Number of 10 subsequences: number of 1s left * number of 0s right
        num_10 = pre1[cut] * suf0[cut]
        err = num_01 * x + num_10 * y
        min_err = min(min_err, err)
    return min_err % MOD
 
print(getMinErrors('0!!1!1', 2, 3))      # Output: 10
print(getMinErrors('!!!!!!', 23, 47))   # Output: 0

ZGVmIGdldE1pbkVycm9ycyhlcnJvclN0cmluZywgeCwgeSk6CiAgICBNT0QgPSAxMCoqOSArIDcKICAgIG4gPSBsZW4oZXJyb3JTdHJpbmcpCiAgICBwcmUwID0gWzBdICogKG4gKyAxKSAgIyBwcmVmaXggY291bnQgb2YgMHMKICAgIHByZTEgPSBbMF0gKiAobiArIDEpICAjIHByZWZpeCBjb3VudCBvZiAxcwogICAgcHJlcSA9IFswXSAqIChuICsgMSkgICMgcHJlZml4IGNvdW50IG9mIHdpbGRjYXJkcwoKICAgICMgQnVpbGQgcHJlZml4IHN1bXMKICAgIGZvciBpIGluIHJhbmdlKG4pOgogICAgICAgIHByZTBbaSsxXSA9IHByZTBbaV0gKyAoMSBpZiBlcnJvclN0cmluZ1tpXSA9PSAnMCcgZWxzZSAwKQogICAgICAgIHByZTFbaSsxXSA9IHByZTFbaV0gKyAoMSBpZiBlcnJvclN0cmluZ1tpXSA9PSAnMScgZWxzZSAwKQogICAgICAgIHByZXFbaSsxXSA9IHByZXFbaV0gKyAoMSBpZiBlcnJvclN0cmluZ1tpXSA9PSAnIScgZWxzZSAwKQoKICAgIHN1ZjAgPSBbMF0gKiAobiArIDEpCiAgICBzdWYxID0gWzBdICogKG4gKyAxKQogICAgc3VmcSA9IFswXSAqIChuICsgMSkKICAgIGZvciBpIGluIHJldmVyc2VkKHJhbmdlKG4pKToKICAgICAgICBzdWYwW2ldID0gc3VmMFtpKzFdICsgKDEgaWYgZXJyb3JTdHJpbmdbaV0gPT0gJzAnIGVsc2UgMCkKICAgICAgICBzdWYxW2ldID0gc3VmMVtpKzFdICsgKDEgaWYgZXJyb3JTdHJpbmdbaV0gPT0gJzEnIGVsc2UgMCkKICAgICAgICBzdWZxW2ldID0gc3VmcVtpKzFdICsgKDEgaWYgZXJyb3JTdHJpbmdbaV0gPT0gJyEnIGVsc2UgMCkKCiAgICAjIENvdW50IHRvdGFsIG51bWJlciBvZiB3aWxkY2FyZHMKICAgIHRvdGFsX3EgPSBwcmVxW25dCgogICAgIyBUcnkgYWxsIHBvc3NpYmxlIGN1dHM6IHdpbGRjYXJkcyBiZWZvcmUgaSBhcmUgJzAnLCBhZnRlciBpIGFyZSAnMScKICAgICMgQW5kIGFsc28gd2lsZGNhcmRzIGJlZm9yZSBpIGFyZSAnMScsIGFmdGVyIGkgYXJlICcwJwogICAgbWluX2VyciA9IGZsb2F0KCdpbmYnKQoKICAgICMgUHJlcGFyZSBmb3IgY3V0OiBhbGwgd2lsZGNhcmRzIGFzICcwJyBvciBhcyAnMScKICAgIGRlZiBjb3VudF9lcnJvcnMoYSwgYik6CiAgICAgICAgIyBDb3VudCBudW1iZXIgb2YgMDEgYW5kIDEwIHN1YnNlcXVlbmNlcwogICAgICAgIGNudDAgPSBjbnQxID0gY250cSA9IDAKICAgICAgICBjbnRfMDEgPSBjbnRfMTAgPSAwCiAgICAgICAgZm9yIGMgaW4gZXJyb3JTdHJpbmc6CiAgICAgICAgICAgIGlmIGMgPT0gJzAnOgogICAgICAgICAgICAgICAgY250MCArPSAxCiAgICAgICAgICAgICAgICBjbnRfMTAgKz0gY250MQogICAgICAgICAgICBlbGlmIGMgPT0gJzEnOgogICAgICAgICAgICAgICAgY250MSArPSAxCiAgICAgICAgICAgICAgICBjbnRfMDEgKz0gY250MAogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgY250MCArPSBhCiAgICAgICAgICAgICAgICBjbnQxICs9IGIKICAgICAgICAgICAgICAgIGNudF8xMCArPSBjbnQxICogYQogICAgICAgICAgICAgICAgY250XzAxICs9IGNudDAgKiBiCiAgICAgICAgcmV0dXJuIGNudF8wMSAqIHggKyBjbnRfMTAgKiB5CgogICAgIyBUcnkgYWxsIHdpbGRjYXJkcyBhcyAnMCcKICAgIGVycjAgPSBjb3VudF9lcnJvcnMoMSwgMCkKICAgICMgVHJ5IGFsbCB3aWxkY2FyZHMgYXMgJzEnCiAgICBlcnIxID0gY291bnRfZXJyb3JzKDAsIDEpCiAgICBtaW5fZXJyID0gbWluKGVycjAsIGVycjEpCgogICAgIyBOb3cgdHJ5IGZvciBhbGwgcG9zc2libGUgY3V0cwogICAgIyBQcmVjb21wdXRlOiBmb3IgZWFjaCBpLCBob3cgbWFueSB3aWxkY2FyZHMgdXAgdG8gaSBhcmUgYXNzaWduZWQgJzAnLCBhZnRlciBhcmUgJzEnCiAgICBwcmVfcTAgPSAwCiAgICBmb3IgY3V0IGluIHJhbmdlKG4gKyAxKToKICAgICAgICB6ZXJvcyA9IHByZTBbY3V0XSArIHByZXFbY3V0XSAgIyAwcyBhbmQgISBhc3NpZ25lZCAwIHRvIHRoZSBsZWZ0CiAgICAgICAgb25lcyA9IHN1ZjFbY3V0XSArIHN1ZnFbY3V0XSAgICMgMXMgYW5kICEgYXNzaWduZWQgMSB0byB0aGUgcmlnaHQKICAgICAgICAjIE51bWJlciBvZiAwMSBzdWJzZXF1ZW5jZXM6IG51bWJlciBvZiAwcyBsZWZ0ICogbnVtYmVyIG9mIDFzIHJpZ2h0CiAgICAgICAgbnVtXzAxID0gemVyb3MgKiBvbmVzCiAgICAgICAgIyBOdW1iZXIgb2YgMTAgc3Vic2VxdWVuY2VzOiBudW1iZXIgb2YgMXMgbGVmdCAqIG51bWJlciBvZiAwcyByaWdodAogICAgICAgIG51bV8xMCA9IHByZTFbY3V0XSAqIHN1ZjBbY3V0XQogICAgICAgIGVyciA9IG51bV8wMSAqIHggKyBudW1fMTAgKiB5CiAgICAgICAgbWluX2VyciA9IG1pbihtaW5fZXJyLCBlcnIpCiAgICByZXR1cm4gbWluX2VyciAlIE1PRAoKcHJpbnQoZ2V0TWluRXJyb3JzKCcwISExITEnLCAyLCAzKSkgICAgICAjIE91dHB1dDogMTAKcHJpbnQoZ2V0TWluRXJyb3JzKCchISEhISEnLCAyMywgNDcpKSAgICMgT3V0cHV0OiAw

MTAKYWJhCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtz

10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks