문제
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와 그의 누나를 도와 이 값을 구해보자.
출력
각 줄에 각 테스트 케이스의 정답인 $F(N, M)$을 출력한다. 단, 이 값이 매우 클 수 있으므로 10ドル^9 + 7$로 나눈 나머지를 출력한다.
제한
1ドル \le T \le 1000$
0ドル \le N \le M \le 10^{18}$
예제 출력 1
복사
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$로 나눈 나머지를 출력함에 유의하자.
W3sicHJvYmxlbV9pZCI6IjI3OTI4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMmU4XHVjODcwIFx1Yzk5ZFx1YWMwMCBcdWMyMTgiLCJkZXNjcmlwdGlvbiI6IjxwPkFsYmVydFx1YjI5NCAmcXVvdDtcdWIyZThcdWM4NzAgXHVjOTlkXHVhYzAwIFx1YzIxOCZxdW90OyAobW9ub3RvbmUgaW5jcmVhc2luZyBudW1iZXIpXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1YyBcdWIxODBcdWM3NzRcdWI5N2MgXHVjOTkwXHVhY2E4XHVkNTVjXHViMmU0LiBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM4MTVcdWMyMTggJHgkXHVjNWQwIFx1YjMwMFx1ZDU3NCAkeCRcdWM3NTggXHVhYzAxIFx1Yzc5MFx1YjlhYyBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NDQgXHVjODhjXHVjZTIxIChcdWFjMDBcdWM3YTUgXHVkMDcwIFx1Yzc5MFx1YjliZlx1YzIxOCkgXHViZDgwXHVkMTMwIFx1YzZiMFx1Y2UyMSAoXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCAxXHVjNzU4IFx1Yzc5MFx1YjliZlx1YzIxOClcdWFlNGNcdWM5YzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Yzc3ZFx1YzVjOFx1Yzc0NCBcdWI1NGMgXHVkNTVjIFx1YmM4OFx1YjNjNCBcdWFjMTBcdWMxOGNcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0ICR4JFx1Yjk3YyBcdWIyZThcdWM4NzAgXHVjOTlkXHVhYzAwIFx1YzIxOFx1Yjc3YyBcdWJkODBcdWI5NzhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgMCwgNSwgMTExLCAyMzQsIDIyNDYgXHViNGYxXHVjNzQwIFx1YjJlOFx1Yzg3MCBcdWM5OWRcdWFjMDAgXHVjMjE4XHVjNzc0XHViYTcwIDEyMSwgNDY1IFx1YjRmMVx1Yzc0MCBcdWIyZThcdWM4NzAgXHVjOTlkXHVhYzAwIFx1YzIxOFx1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkFsYmVydFx1YWMwMCBcdWQzYzlcdWMxOGMgXHVjOTkwXHVhY2E4XHVkNTU4XHViMjk0IFx1YjE4MFx1Yzc3NFx1YjI5NCBcdWM3ODRcdWM3NThcdWM3NTggXHVjODE1XHVjMjE4ICR4JFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCAkeCRcdWI5N2MgXHVjZDA4XHVhY2ZjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YjJlOFx1Yzg3MCBcdWM5OWRcdWFjMDAgXHVjMjE4XHViOTdjIFx1Y2MzZVx1YjI5NCBcdWIxODBcdWM3NzRcdWM3NzRcdWIyZTQgLS0gXHVkM2I4XHVjNzU4XHVjMGMxIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM4MTVcdWMyMThcdWI5N2MgJFMoeCkkXHViNzdjIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YzgxNVx1Yzc1OFx1YzVkMCBcdWI1MzBcdWI5NzRcdWJhNzQgJHgkXHVhYzAwIFx1YjJlOFx1Yzg3MCBcdWM5OWRcdWFjMDAgXHVjMjE4XHViNzdjXHViYTc0IFx1YjJmOVx1YzVmMFx1ZDc4OCAkUyh4KSA9IHgkXHVjNzc0XHViYTcwICRTKDUpID0gNSRcdWM2NDAgJFMoMTExKSA9IDExMSQgXHViNGYxXHVjNzc0IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTVjXHViMmU0LiBcdWJjMThcdWJhNzQsICR4JFx1YWMwMCBcdWIyZThcdWM4NzAgXHVjOTlkXHVhYzAwIFx1YzIxOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVhY2JkXHVjNmIwXHViMjk0IFx1YjJmOVx1YzVmMFx1ZDc4OCAkUyh4KSBcXGx0IHgkXHVjNzc0XHViYTcwLCAkUygxMjEpID0gMTE5JCBcdWM2NDAgJFMoNDY1KSA9IDQ1OSQgXHViNGYxXHVjNzc0IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5BbGJlcnRcdWM3NTggXHViMTgwXHVjNzc0XHViOTdjIFx1YzljMFx1Y2YxY1x1YmNmNFx1YjM1OCBcdWFkZjhcdWM3NTggXHViMjA0XHViMDk4XHViMjk0IFx1Yzg3MFx1YWUwOCBcdWIzNTQgXHVjN2FjXHViYmY4XHVjNzg4XHViMjk0IFx1YjE4MFx1Yzc3NFx1Yjk3YyBcdWM4MWNcdWM1NDhcdWQ1ODhcdWIyZTQuIDAgXHVjNzc0XHVjMGMxXHVjNzc4IFx1YjQ1MCBcdWM4MTVcdWMyMTggJE4gXFxsZSBNJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCAkRihOLCBNKSA9IFxcc3VtX3t4PU59XntNfSBTKHgpJCBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1YjE4MFx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCAkTiRcdWM3NzRcdWMwYzEgJE0kXHVjNzc0XHVkNTU4XHVjNzc4IFx1YmFhOFx1YjRlMCBcdWM4MTVcdWMyMThcdWM1ZDAgJHgkIFx1YjMwMFx1ZDU3NCAkUyh4KSRcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNWVjIFx1YjM1NFx1ZDU1YyBcdWFjMTJcdWM3NzQgJEYoTiwgTSkkXHVjNzc0IFx1YjQxY1x1YjJlNC4gQWxiZXJ0XHVjNjQwIFx1YWRmOFx1Yzc1OCBcdWIyMDRcdWIwOThcdWI5N2MgXHViM2M0XHVjNjQwIFx1Yzc3NCBcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1IFx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggJFQkIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkVCRcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWM5MDRcdWM1ZDAgJE4sIE0kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjODE1XHViMmY1XHVjNzc4ICRGKE4sIE0pJFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVjNzc0IFx1YWMxMlx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVkMDc0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgJDEwXjkgKyA3JFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDEgXFxsZSBUIFxcbGUgMTAwMCQ8XC9saT5cclxuXHQ8bGk+JDAgXFxsZSBOIFxcbGUgTSBcXGxlIDEwXnsxOH0kPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+XHVjNjA4XHVjODFjIDEtMjogXHViY2Y4XHViYjM4XHVjNWQwXHVjMTFjIFx1YjJlNFx1YjhlOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHVjODFjIDM6ICQ0MiBcXGxlIHggXFxsZSA1MCRcdWM3NzggJFMoeCkkXHVjNzU4IFx1YWMxMlx1Yzc0MCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgJDM5LCAzOSwgNDQsIDQ1LCA0NiwgNDcsIDQ4LCA0OSwgNDkkIFx1Yzc3NFx1YmJjMFx1Yjg1YyBcdWNkMWRcdWQ1NjlcdWM3NzggNDA2XHVjNzc0IFx1YzgxNVx1YjJmNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHVjODFjIDQ6IFx1YjJmNVx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVjZWU0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgJDEwXjkgKyA3JFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU2OFx1YzVkMCBcdWM3MjBcdWM3NThcdWQ1NThcdWM3OTAuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMjc5MjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNb25vdG9uZSBJbmNyZWFzaW5nIE51bWJlciIsImRlc2NyaXB0aW9uIjoiPHA+QWxiZXJ0IGxpa2VzIHRvIHBsYXkgd2l0aCAmcXVvdDttb25vdG9uZSBpbmNyZWFzaW5nIG51bWJlcnMuJnF1b3Q7IEZvciBhbiBhcmJpdHJhcnkgbm9uLW5lZ2F0aXZlIG51bWJlciAkeCQsIGlmIHRoZSBkaWdpdHMgaW4gJHgkIGZyb20gbGVmdC1tb3N0ICh0aGUgaGlnaGVzdCBwbGFjZSBkaWdpdCkgdG8gcmlnaHQtbW9zdCAob25lJiMzOTtzIHBsYWNlIGRpZ2l0KSBhcmUgbmV2ZXIgZGVjcmVhc2luZywgdGhlbiAkeCQgaXMgc2FpZCB0byBiZSBhIG1vbm90b25lIGluY3JlYXNpbmcgbnVtYmVyLiBGb3IgaW5zdGFuY2UsIDAsIDUsIDExMSwgMjM0LCBhbmQgMjI0NiBhcmUgbW9ub3RvbmUgaW5jcmVhc2luZyBudW1iZXJzIHdoZXJlYXMgMTIxIGFuZCA0NTYgYXJlIG5vdC48XC9wPlxyXG5cclxuPHA+QWxiZXJ0IGxpa2VzIHRvIHBsYXkgYSBnYW1lIHdoZXJlLCBnaXZlbiBhbiBhcmJpdHJhcnkgaW50ZWdlciAkeCQsIGhlIGZpbmRzIHRoZSBsYXJnZXN0IG1vbm90b25lIGluY3JlYXNpbmcgbnVtYmVyIHRoYXQgZG9lcyBub3QgZXhjZWVkICR4JCAtLSBsZXQgdXMgY2FsbCBzdWNoIG51bWJlciAkUyh4KSQgZm9yIGNvbnZlbmllbmNlLiBBY2NvcmRpbmcgdG8gdGhpcyBkZWZpbml0aW9uLCB3ZSBoYXZlICRTKHgpID0geCQgd2hlbiAkeCQgaXMgYSBtb25vdG9uZSBpbmNyZWFzaW5nIG51bWJlciwgYW5kJm5ic3A7JFMoNSkgPSA1JCBhbmQgJFMoMTExKSA9IDExMSQgYXJlIHR3byBleGFtcGxlcy4gT24gdGhlIG90aGVyIGhhbmQsIGlmICR4JCBpcyBub3QgYSBtb25vdG9uZSBpbmNyZWFzaW5nIG51bWJlciB0aGVuIHRyaXZpYWxseSAkUyh4KSBcXGx0IHgkLCBhbmQgZXhhbXBsZXMgaW5jbHVkZSAkUygxMjEpID0gMTE5JCBhbmQgJFMoNDY1KSA9IDQ1OSQuPFwvcD5cclxuXHJcbjxwPldoaWxlIHdhdGNoaW5nIGhvdyBBbGJlcnQgcGxheXMgdGhpcyBnYW1lLCBoaXMgc2lzdGVyIHN1Z2dlc3RlZCBhIG1vcmUgZnVuIGdhbWU6Jm5ic3A7R2l2ZW4gdHdvIGludGVnZXJzICROIFxcbGUgTSQgdGhhdCBhcmUgbm8gbGVzcyB0aGFuIDAsIGZpbmQgJEYoTiwgTSkgPSBcXHN1bV97eD1OfV57TX0gUyh4KSQuIFRoYXQgaXMsICRGKE4sIE0pJCBpcyB0aGUgc3VtIG9mIGFsbCAkUyh4KSQmIzM5O3MgZm9yICR4JCBiZXR3ZWVuICROJCBhbmQgJE0kLCBpbmNsdXNpdmUuIExldCYjMzk7cyBjb21wdXRlIHRoaXMgdmFsdWUgYW5kIGhlbHAgQWxiZXJ0IGFuZCBoaXMgc2lzdGVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IHdpbGwgY29udGFpbiAkVCQsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nICRUJCBsaW5lcyB3aWxsIGNvbnRhaW4gJE4kIGFuZCAkTSQsIHNlcGFyYXRlZCBieSB3aGl0ZXNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0ICRGKE4sIE0pJCBpbiBlYWNoIGxpbmUuIFNpbmNlIHRoZSBhbnN3ZXIgbWF5IGJlIHRvbyBsYXJnZSwgb3V0cHV0IHRoZSBhbnN3ZXIgbW9kdWxvICQxMF45ICsgNyQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIFQgXFxsZSAxMDAwJDxcL2xpPlxyXG5cdDxsaT4kMCZuYnNwO1xcbGUgTiBcXGxlIE0gXFxsZSAxMF57MTh9JDxcL2xpPlxyXG48XC91bD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPkNhc2VzIDEtMjogRGlzY3Vzc2VkIGluIHRoZSBwcm9ibGVtIHN0YXRlbWVudC48XC9wPlxyXG5cclxuPHA+Q2FzZSAzOiBGb3IgZWFjaCAkeCQgd2l0aCAkNDIgXFxsZSB4IFxcbGUgNTAkLCB0aGUgdmFsdWVzIG9mICRTKHgpJCBhcmU6ICQzOSwgMzksIDQ0LCA0NSwgNDYsIDQ3LCA0OCwgNDksIDQ5JC4gSGVuY2UsIHRoZSBhbnN3ZXIgaXMgdGhlIHN1bSBvZiB0aGVzZSB2YWx1ZXMsIDQwNi48XC9wPlxyXG5cclxuPHA+Q2FzZSA0OiBSZWNhbGwgdGhhdCB5b3UgbXVzdCBvdXRwdXQgdGhlIGFuc3dlciBtb2R1bG8gJDEwXjkgKyA3JC48XC9wPlxyXG4ifV0=