RoAlgo Contest #4 (incepatori) | trap

Given the natural number $N$ and the binary strings of length $N$: $L$ and $R$ ($L \leq R$).

Task

Find how many pairs $(a, b)$ satisfy the following criteria:

1. $L \leq a, b \leq R$
2. $(a \otimes b) + (a \ \& \ b) = (a + b)$

Where $\otimes$ represents the XOR operation on bits, and $\&$ represents the AND operation on bits.

Input data

The first line contains the number $N$. The second line contains the number $L$ in base $2$. The third line contains the number $R$ in base $2$.

Output data

The first line contains a single natural number, representing the answer, modulo $10^9 + 7$.

Constraints and clarifications

• $1 \leq N \leq 200 \ 000$

Example

stdin

4
0100
1101

stdout

18

Explanation

There are $18$ pairs $(a, b)$ of natural numbers that meet the conditions. These pairs are:

1. $(4, 8)$
2. $(4, 9)$
3. $(4, 10)$
4. $(4, 11)$
5. $(5, 8)$
6. $(5, 10)$
7. $(6, 8)$
8. $(6, 9)$
9. $(7, 8)$
10. $(8, 4)$
11. $(8, 5)$
12. $(8, 6)$
13. $(8, 7)$
14. $(9, 4)$
15. $(9, 6)$
16. $(10, 4)$
17. $(10, 5)$
18. $(11, 4)$

$18 = 18 \mod 10^9 + 7$, therefore the answer is $18$.