409189: GYM103451 I Krosh and bit operations

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 $$$.

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 answer modulo $$$10^9+7$$$.

4
001
101
100

8