H. Самоисследование
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заскучав от постоянного исследования Луны, Wall-B решил исследовать то, из чего он сделан — двоичные числа. Он взял двоичное число и решил посчитать, сколько раз в нем появлялись разные подстроки длины два. Он хранит эти значения в $$$c_{00}$$$, $$$c_{01}$$$, $$$c_{10}$$$ и $$$c_{11}$$$, описывающих, сколько раз в числе встречаются подстроки 00, 01, 10 и 11, соответственно. Например:

$$$10111100 \rightarrow c_{00} = 1, \ c_{01} = 1,\ c_{10} = 2,\ c_{11} = 3$$$

$$$10000 \rightarrow c_{00} = 3,\ c_{01} = 0,\ c_{10} = 1,\ c_{11} = 0$$$

$$$10101001 \rightarrow c_{00} = 1,\ c_{01} = 3,\ c_{10} = 3,\ c_{11} = 0$$$

$$$1 \rightarrow c_{00} = 0,\ c_{01} = 0,\ c_{10} = 0,\ c_{11} = 0$$$

Wall-B заметил, что может быть несколько двоичных чисел с одинаковыми $$$c_{00}$$$, $$$c_{01}$$$, $$$c_{10}$$$, $$$c_{11}$$$. Поэтому он хочет посчитать, сколько двоичных чисел из отрезка $$$[A, B]$$$ имеют данные $$$c_{xy}$$$. К сожалению, его вычислительная мощность недостаточно сильна для обработки таких больших, интересных ему интервалов. Можете ли вы ему помочь? Поскольку это число может быть большим, выведите его по модулю $$$10^9 + 7$$$.

Входные данные

Первые две строки содержат два положительных двоичных целых числа $$$A$$$ и $$$B$$$ ($$$1 \leq A \leq B < 2^{100\,000}$$$), описывающих начало и конец отрезка, соответственно. Двоичные числа $$$A$$$ и $$$B$$$ не содержат лидирующих нулей.

Следующие четыре строки содержат целые числа $$$c_{00}$$$, $$$c_{01}$$$, $$$c_{10}$$$, $$$c_{11}$$$ ($$$0 \leq c_{00}, c_{01}, c_{10}, c_{11} \leq 100\,000$$$) описывающие количество вхождений подстрок 00, 01, 10 и 11, соответственно.

Выходные данные

Выведите одно число, описывающее количество чисел из отрезка $$$[A, B]$$$, удовлетворяющих условию, по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
10
1001
0
0
1
1
Выходные данные
1
Входные данные
10
10001
1
2
3
4
Выходные данные
0
Примечание

Пример 1: Двоичные числа из отрезка $$$[10,1001]$$$ это $$$10,11,100,101,110,111,1000,1001$$$. Только число 110 удовлетворяет данным ограничениям: $$$c_{00} = 0, c_{01} = 0, c_{10} = 1, c_{11} = 1$$$.

Пример 2: Никакое число из этого отрезка не удовлетворяет данным условиям.