아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

흥미로운 수

시간 제한1초메모리 제한512 MB

요약
L과 R 사이에서 각 자릿수가 감소하지 않는 양의 정수의 개수를 10^9+7로 나눈 나머지를 구한다. L과 R은 10^100까지이다.
난이도

보통10점 중 7점

유형
동적 계획법, 조합론, 수학, 구현
정답자
아직 제출이 없습니다

문제

소피아는 어떤 수의 자릿수가 감소하지 않는 순서로 나열되어 있으면 그 수를 흥미롭다고 생각한다. 예를 들어 123, 1111, 888999는 흥미로운 수이다.

소피아는 LL 이상 RR 이하인 흥미로운 양의 정수가 몇 개인지 궁금해졌다. LL과 RR이 크면 그 개수가 상당히 커질 수 있으므로, 소피아는 이 개수를 109+710^9 + 7로 나눈 나머지를 구하려고 한다.

주어진 LL과 RR에 대해 LL 이상 RR 이하인 흥미로운 수의 개수를 구하고, 그 개수를 109+710^9 + 7로 나눈 나머지를 출력하는 프로그램을 작성하라.

입력

입력 파일은 두 줄로 이루어진다. 첫째 줄에는 수 LL이, 둘째 줄에는 수 RR이 주어진다 (1≤L≤R≤101001 \le L \le R \le 10^{100}).

출력

출력 파일에는 LL 이상 RR 이하인 흥미로운 수의 개수를 109+710^9 + 7로 나눈 나머지인 정수 하나를 출력한다.

예제1

  1. 예제 1

    입력
    1
    100
    
    예상 출력
    54