Min Total Errors

Replace each ! with 0 or 1. For every pair of indices i<j, a 01 pair contributes x and a 10 pair contributes y; this is not limited to adjacent characters. First minimize the full error total, then take it modulo 1000000007 at the end. This page only kept prose; this site restored the formal subsequence and modulus rules from the same problem with the same example 101!1 in amazon-get-min-errors.md of the same snapshot, and binds both raw sources as evidence.

输入格式

The first line contains errorString and the second line contains x y. The main raw gives no value bounds; the supplementary raw specifies length 1..100000 and costs 0..100000. This site fully covers that range and extends the costs to 0≤x,y≤10^9. The string contains only 0, 1 and !. A typo in the supplementary raw that printed the character l is restored to ! based on the body and all examples.

输出格式

Output a single integer, the answer.

样例 1

输入：

101!1
2 3

输出：

9

样例 2

输入：

!1
1 1

输出：

0

样例 3

输入：

1!0
4 0

输出：

0

样例说明

The answers are 9, 0 and 0 respectively. In the second example you should choose 11; you cannot look only at the prefix and greedily set the first position to 0. In the third example the cost of 10 is 0, which is valid.