| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 62 | 21 | 17 | 35.417% |
Albert는 "단조 증가 수" (monotone increasing number)를 이용한 놀이를 즐겨한다. 음이 아닌 임의의 정수 $x$에 대해 $x$의 각 자리 숫자들을 좌측 (가장 큰 자릿수) 부터 우측 (가장 작은 1의 자릿수)까지 순서대로 읽었을 때 한 번도 감소하지 않으면 $x$를 단조 증가 수라 부른다. 예를 들어 0, 5, 111, 234, 2246 등은 단조 증가 수이며 121, 465 등은 단조 증가 수가 아니다.
Albert가 평소 즐겨하는 놀이는 임의의 정수 $x$가 주어졌을 때, $x$를 초과하지 않으면서 가장 큰 단조 증가 수를 찾는 놀이이다 -- 편의상 그러한 정수를 $S(x)$라 하자. 이 정의에 따르면 $x$가 단조 증가 수라면 당연히 $S(x) = x$이며 $S(5) = 5$와 $S(111) = 111$ 등이 이러한 경우에 해당한다. 반면, $x$가 단조 증가 수가 아닌 경우는 당연히 $S(x) \lt x$이며, $S(121) = 119$ 와 $S(465) = 459$ 등이 이러한 경우에 해당한다.
Albert의 놀이를 지켜보던 그의 누나는 조금 더 재미있는 놀이를 제안했다. 0 이상인 두 정수 $N \le M$이 주어졌을 때, $F(N, M) = \sum_{x=N}^{M} S(x)$ 를 구하는 놀이이다. 즉, $N$이상 $M$이하인 모든 정수에 $x$ 대해 $S(x)$를 구하여 더한 값이 $F(N, M)$이 된다. Albert와 그의 누나를 도와 이 값을 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.
다음 $T$줄에 걸쳐 각 줄에 $N, M$이 공백으로 구분되어 주어진다.
각 줄에 각 테스트 케이스의 정답인 $F(N, M)$을 출력한다. 단, 이 값이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.
4 121 121 465 465 42 50 11111122222233333 12345612345612345
119 459 406 740694249
예제 1-2: 본문에서 다루었다.
예제 3: $42 \le x \le 50$인 $S(x)$의 값은 순서대로 $39, 39, 44, 45, 46, 47, 48, 49, 49$ 이므로 총합인 406이 정답이다.
예제 4: 답이 매우 커질 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력함에 유의하자.