trap

Time limit: 0.5s Memory limit: 128MB Input: Output:

Given the natural number NN and the binary strings of length NN: LL and RR (LRL \leq R).

Task

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

  1. La,bRL \leq a, b \leq R
  2. (ab)+(a & b)=(a+b)(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 NN. The second line contains the number LL in base 22. The third line contains the number RR in base 22.

Output data

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

Constraints and clarifications

  • 1N200 0001 \leq N \leq 200 \ 000

Example

stdin

4
0100
1101

stdout

18

Explanation

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

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

18=18mod109+718 = 18 \mod 10^9 + 7, therefore the answer is 1818.

Log in or sign up to be able to send submissions!