Get Minimum Errors

Replace each ! independently with 0 or 1. Every pair of indices i<j that forms 01 contributes x, and every pair that forms 10 contributes y; this is not limited to adjacent characters. Minimize the full cost, then take it modulo 1000000007.

输入格式

The first line contains a non-empty string consisting only of 0, 1 and !; the second line contains x y. Length ≤100000, 0≤x,y≤100000.

输出格式

Output a single integer, the answer.

样例 1

输入：

101!1
2 3

输出：

9

样例 2

输入：

!1
1 1

输出：

0

样例 3

输入：

01!0
2 2

输出：

6

样例说明

The answers are 9, 0 and 6; in the second example, replacing to get 11 produces no errors.