def getMinErrors(errorString, x, y):
    MOD = 10**9 + 7
 
    # dp0 = (min errors ending with '0', zeros, ones)
    # dp1 = (min errors ending with '1', zeros, ones)
    dp0 = (0, 0, 0)
    dp1 = (0, 0, 0)
 
    for c in errorString:
        if c == '0':
            new_dp0 = (dp0[0] + y * dp0[2], dp0[1] + 1, dp0[2])
            new_dp1 = (float('inf'), 0, 0)
        elif c == '1':
            new_dp0 = (float('inf'), 0, 0)
            new_dp1 = (dp1[0] + x * dp1[1], dp1[1], dp1[2] + 1)
        else:  # '!'
            # Try as '0'
            cand0_1 = (dp0[0] + y * dp0[2], dp0[1] + 1, dp0[2])
            cand0_2 = (dp1[0] + y * dp1[2], dp1[1] + 1, dp1[2])
            best0 = cand0_1 if cand0_1[0] < cand0_2[0] else cand0_2
 
            # Try as '1'
            cand1_1 = (dp0[0] + x * dp0[1], dp0[1], dp0[2] + 1)
            cand1_2 = (dp1[0] + x * dp1[1], dp1[1], dp1[2] + 1)
            best1 = cand1_1 if cand1_1[0] < cand1_2[0] else cand1_2
 
            new_dp0 = best0
            new_dp1 = best1
 
        dp0 = (new_dp0[0] % MOD, new_dp0[1], new_dp0[2])
        dp1 = (new_dp1[0] % MOD, new_dp1[1], new_dp1[2])
 
    return min(dp0[0], dp1[0]) % MOD
 
print(getMinErrors('0!!1!1', 2, 3))      # Output: 10
print(getMinErrors('!!!!!!', 23, 47))   # Output: 0
print(getMinErrors('1011!', 2, 3))      # Output: 9

ZGVmIGdldE1pbkVycm9ycyhlcnJvclN0cmluZywgeCwgeSk6CiAgICBNT0QgPSAxMCoqOSArIDcKCiAgICAjIGRwMCA9IChtaW4gZXJyb3JzIGVuZGluZyB3aXRoICcwJywgemVyb3MsIG9uZXMpCiAgICAjIGRwMSA9IChtaW4gZXJyb3JzIGVuZGluZyB3aXRoICcxJywgemVyb3MsIG9uZXMpCiAgICBkcDAgPSAoMCwgMCwgMCkKICAgIGRwMSA9ICgwLCAwLCAwKQoKICAgIGZvciBjIGluIGVycm9yU3RyaW5nOgogICAgICAgIGlmIGMgPT0gJzAnOgogICAgICAgICAgICBuZXdfZHAwID0gKGRwMFswXSArIHkgKiBkcDBbMl0sIGRwMFsxXSArIDEsIGRwMFsyXSkKICAgICAgICAgICAgbmV3X2RwMSA9IChmbG9hdCgnaW5mJyksIDAsIDApCiAgICAgICAgZWxpZiBjID09ICcxJzoKICAgICAgICAgICAgbmV3X2RwMCA9IChmbG9hdCgnaW5mJyksIDAsIDApCiAgICAgICAgICAgIG5ld19kcDEgPSAoZHAxWzBdICsgeCAqIGRwMVsxXSwgZHAxWzFdLCBkcDFbMl0gKyAxKQogICAgICAgIGVsc2U6ICAjICchJwogICAgICAgICAgICAjIFRyeSBhcyAnMCcKICAgICAgICAgICAgY2FuZDBfMSA9IChkcDBbMF0gKyB5ICogZHAwWzJdLCBkcDBbMV0gKyAxLCBkcDBbMl0pCiAgICAgICAgICAgIGNhbmQwXzIgPSAoZHAxWzBdICsgeSAqIGRwMVsyXSwgZHAxWzFdICsgMSwgZHAxWzJdKQogICAgICAgICAgICBiZXN0MCA9IGNhbmQwXzEgaWYgY2FuZDBfMVswXSA8IGNhbmQwXzJbMF0gZWxzZSBjYW5kMF8yCgogICAgICAgICAgICAjIFRyeSBhcyAnMScKICAgICAgICAgICAgY2FuZDFfMSA9IChkcDBbMF0gKyB4ICogZHAwWzFdLCBkcDBbMV0sIGRwMFsyXSArIDEpCiAgICAgICAgICAgIGNhbmQxXzIgPSAoZHAxWzBdICsgeCAqIGRwMVsxXSwgZHAxWzFdLCBkcDFbMl0gKyAxKQogICAgICAgICAgICBiZXN0MSA9IGNhbmQxXzEgaWYgY2FuZDFfMVswXSA8IGNhbmQxXzJbMF0gZWxzZSBjYW5kMV8yCgogICAgICAgICAgICBuZXdfZHAwID0gYmVzdDAKICAgICAgICAgICAgbmV3X2RwMSA9IGJlc3QxCgogICAgICAgIGRwMCA9IChuZXdfZHAwWzBdICUgTU9ELCBuZXdfZHAwWzFdLCBuZXdfZHAwWzJdKQogICAgICAgIGRwMSA9IChuZXdfZHAxWzBdICUgTU9ELCBuZXdfZHAxWzFdLCBuZXdfZHAxWzJdKQoKICAgIHJldHVybiBtaW4oZHAwWzBdLCBkcDFbMF0pICUgTU9ECgpwcmludChnZXRNaW5FcnJvcnMoJzAhITEhMScsIDIsIDMpKSAgICAgICMgT3V0cHV0OiAxMApwcmludChnZXRNaW5FcnJvcnMoJyEhISEhIScsIDIzLCA0NykpICAgIyBPdXRwdXQ6IDAKcHJpbnQoZ2V0TWluRXJyb3JzKCcxMDExIScsIDIsIDMpKSAgICAgICMgT3V0cHV0OiA5

MTAKYWJhCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtzCmdlZWtzZm9yZ2Vla3MKZ2Vla3Nmb3JnZWVrcwpnZWVrc2ZvcmdlZWtz

10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks