Count Odd Even Numbers :
Difficulty Level : Medium
Submissions : 900
Asked In :
Marks :10
: 16 | : 2
Given an integer $$$p$$$, and two large numbers in the form of string $$$L$$$ and $$$R$$$.
Count the number of values between $$$L$$$ to $$$R$$$ (both inclusive) that are divisible by $$$p$$$, and the number should have even value at the odd indices and odd values in the even indices.
Input
The first line contains an integer $$$p(1 \le p \le 25)$$$
The second line contains $$$L(1 \le L \le 10^{99})$$$
The third line contains $$$R(L \le R \le 10^{99})$$$
Output
Output the answer modulo $$$10^{9}+7$$$
Examples
Input
7 1 25
Output
2
Input
2 8 15
Output
0
Note
In the given sample case, there are 3 numbers divisible by 7 in the range of 1 to 25.
- 7 - at index 0(even), we have value 7(odd).
- 14 - at index 0(even), we have value 4(even), so do not count
- 21 - at index 0(even), we have value 1(odd) and at index 1(odd), we have value 2(even).
