A number, , is called irresponsible when adding to requires a carry operation. For example, , , and are irresponsible numbers because adding them to , , and (respectively) requires a carry operation:
- In , a is carried over into the 's place.
- In , a is carried over into the 's place.
- In , a is carried over into the 's place.
You have two integers, and . Construct a new number, , by repeating a total of times. For example, if and , then .
Given and , construct and find all the irreponsible numbers between and . Then print the number of irresponsible numbers in the aforementioned range; as this number can be quite large, your answer must be modulo .
Input Format
A single line with two space-separated integers denoting the respective values of and .
Constraints
Subtasks
For of the maximum score:
For of the maximum score:
Output Format
Print a single integer denoting the number of irresponsible numbers between and , modulo .
Sample Input
1 2
Sample Output
4
Explanation
When we repeat a total of times we get . The irresponsible numbers between and are , , , and . Because there are four irresponsible numbers, we print on a new line.