Weighted 01 and 10 subsequence pairs with wildcards

A status string holds '0', '1' and '!'. Every pair of positions i < j that reads 0 then 1 (a subsequence, not a substring) costs x, and every pair that reads 1 then 0 costs y. Replace each '!' with 0 or 1 to get the best total cost (the report asks for the extreme value; work out the minimum and say what changes for the maximum), modulo 10^9 + 7. Trying every replacement is exponential; find a linear or near-linear approach.