Строка из 0, 1 и !: минимальная стоимость ошибок

Senior PRO

Задача

Дана строка из символов 0, 1 и ! (каждый ! можно заменить на 0 или 1), и числа x, y. Каждая подпоследовательность 01 (ноль раньше единицы) стоит x, каждая 10 — y. Верни минимальную суммарную стоимость по модулю 10⁹.

• "01!!", x = 2, y = 3 → 6 (вариант 0111: три пары 01 × 2).
• "!!!!", x = 2, y = 5 → 0 (все одинаковые — пар нет).
• Длина до 50 000.