409189: GYM103451 I Krosh and bit operations

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Krosh and bit operationstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Krosh has three numbers $$$ a $$$, $$$ b $$$, $$$ c $$$. Help him count the number of arrays of length $$$ n $$$, whose $$$ AND $$$ of elements is equal to $$$ a $$$, $$$ OR $$$ of elements is equal to $$$ b $$$, and $$$ XOR $$$ of elements is equal to $$$ c $$$. Two arrays are considered different if there is a position such that different arrays have different numbers at this position. Since the answer can get big, print its remainder after division by $$$ 10 ^ 9 + 7 $$$.

Input

The first line contains the number of elements in the array $$$ 1 \le n \le 10 ^ {18} $$$. The second line contains the number $$$ a $$$. The third line contains the number $$$ b $$$. The fourth line contains the number $$$ c $$$. These numbers are written in binary notation, their lengths are equal and do not exceed $$$ 10 ^ 5 $$$. It is guaranteed that the number $$$ b $$$ denoting $$$ OR $$$ starts with $$$ 1 $$$. The numbers $$$ a $$$ and $$$ c $$$ may contain leading zeros.

Output

Output answer modulo $$$10^9+7$$$.

ExampleInput
4
001
101
100
Output
8

加入题单

上一题 下一题 算法标签: