Se dă numărul natural $N$ și șirurile binare de lungime $N$: $L$, $R$ ($L \leq R$).

Cerință

Să se afle câte perechi $(a, b)$ respectă următorul criteriu:

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

Unde $\otimes$ reprezintă operația XOR pe biți, iar $\&$ reprezintă operația ȘI pe biți.

Date de intrare

Pe prima linie se află numărul $N$. Pe a doua linie se află numărul L, în baza 2. Pe a treia linie se află numărul R, în baza 2.

Date de ieșire

Pe prima linie se află un singur număr natural, reprezentând răspunsul, modulo $10^9 + 7$.

Restricții și precizări

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

Exemplu

stdin

4
0100
1101

stdout

18

Explicație

Sunt $18$ perechi $(a, b)$ de numere naturale care respectă condițiile. Aceste perechi sunt:

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$, așadar răspunsul este $18$.