I. Крош и задача на битовые операции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кроша есть три числа $$$a$$$, $$$b$$$, $$$c$$$. Помогите ему посчитать количество массивов длиной $$$n$$$, $$$AND$$$ элементов которых равен $$$a$$$, $$$OR$$$ элементов которых равен $$$b$$$, $$$XOR$$$ элементов которых равен $$$c$$$. Два массива считаются различными, если существует позиция, что в разных массивах на этой позиции стоят разные числа. Так как ответ может получиться большим, выведите его остаток от деления на $$$10^9+7$$$.

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

В первой строке дано количество элементов в массиве $$$1 \le n \le 10^{18}$$$. Во второй строке дано число $$$a$$$. В третьей строке дано число $$$b$$$. В четвертой строке дано число $$$c$$$. Эти числа записаны в двоичной системе счисления, их длины равны и не превосходят $$$10^5$$$. Гарантируется, что число $$$b$$$, обозначающее $$$OR$$$, начинается с $$$1$$$. В числах $$$a$$$ и $$$c$$$ могут быть лидирующие нули.

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

Выведите ответ на задачу по модулю $$$10^9+7$$$.

Пример
Входные данные
4
001
101
100
Выходные данные
8