시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 81 | 22 | 13 | 23.636% |
Your friend, Mirek, had some files containing integers. He had to sort integers in each file in ascending order. Mirek is an IT specialist so, of course, he tried to find a command line tool that would do his task. The name of a tool wasn’t hard to guess, but it didn’t work as Mirek expected – after sorting the files, he realized that this tool was treating every integer as a string and it sorted them lexicographically. He knew that such a thing could happen, but he was surprised anyway – these files were still sorted in ascending order.
Now, Mirek wonders how lucky he was and how was even possible that integers from these files could have had same lexicographical and numerical order. Help him satisfy his curiosity.
Given a range of integers [A, B], determine the number of subsets of those integers, that their lexicographical and numerical orders are equal.
On the first and only line of input there are two integers A and B (1 ≤ A ≤ B ≤ 1018 , B − A ≤ 105).
Output a single line with integer M, where M is the number of subsets of set {A, A+ 1, . . . , B}, which keep specified condition. As the answer may be really big, output it modulo 109 + 7.
98 101
7
Those subsets are: ∅, {98}, {99}, {100}, {101}, {98, 99}, {100, 101}.