getMinErrors

Replace each ! with 0 or 1; every index pair i<j forming 01 costs x, and every pair forming 10 costs y. First find the minimum total cost, then take it modulo 10⁹+7; do not compare costs after taking the modulus.

输入格式

The first line contains errorString (length 1..100000), and the second line contains x y (0..10⁹).

输出格式

Output a single integer answer.

样例 1

输入：

!!!!!!!
23 47

输出：

0

样例 2

输入：

0!1
2 5

输出：

4

样例 3

输入：

10
2 5

输出：

5

样例说明

Example 1: set everything to 0; there are no pairs of different values, cost 0. Example 2: choosing 001 or 011 both produce two 01 pairs, cost 4. Example 3: the only 10 subsequence costs 5.