시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB78433257.143%

문제

두 정수의 거리는 각 자리의 차이의 절댓값의 합으로 정의할 수 있다. 예를 들어, 4561과 3278의 거리는 |4 - 3| + |5 - 2| + |6 - 7| + |1 - 8| = 12 이다. 두 정수의 길이가 일치하지 않는 경우에는 앞에 0을 붙인다. 따라서, 32와 5678의 거리는 |0 - 5| + |0 - 6| + |3 - 7| + |2 - 8| = 21이 된다.

두 정수 A와 B가 주어졌을 때, 구간 [A,B]에 포함되는 모든 쌍의 거리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 A와 B가 주어진다. (1 ≤ A ≤ B ≤ 1050000)

출력

첫째 줄에 구간 [A,B]에 포함되는 모든 쌍의 거리의 합을 출력한다. 답이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

1 5

예제 출력 1

40

예제 입력 2

288 291

예제 출력 2

76

(288, 289) = 1, (288, 290) = 9, (288, 291) = 8, (289, 290) = 10, (289, 291) = 9, (290, 291) = 1. 각 쌍을 두 번씩 더하면 2 * (1 + 9 + 8 + 10 + 9 + 1) = 76.

예제 입력 3

1000000 10000000

예제 출력 3

581093400
W3sicHJvYmxlbV9pZCI6Ijk2MjkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI0NTAgXHVjODE1XHVjMjE4XHVjNzU4IFx1YWM3MFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHViNDUwIFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHVhYzAxIFx1Yzc5MFx1YjlhY1x1Yzc1OCBcdWNjMjhcdWM3NzRcdWM3NTggXHVjODA4XHViMzEzXHVhYzEyXHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgNDU2MVx1YWNmYyAzMjc4XHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCB8NCAtIDN8ICsgfDUgLSAyfCArIHw2IC0gN3wgKyB8MSAtIDh8ID0gMTIgXHVjNzc0XHViMmU0LiBcdWI0NTAgXHVjODE1XHVjMjE4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM3N2NcdWNlNThcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NWVcdWM1ZDAgMFx1Yzc0NCBcdWJkOTlcdWM3NzhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgMzJcdWM2NDAgNTY3OFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgfDAgLSA1fCArIHwwIC0gNnwgKyB8MyAtIDd8ICsgfDIgLSA4fCA9IDIxXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzgxNVx1YzIxOCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZDZjXHVhYzA0IFtBLEJdXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMzBkXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBICZsZTsgQiAmbGU7IDEwPHN1cD41MDAwMDxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFkNmNcdWFjMDQgW0EsQl1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM3NTggXHVhYzcwXHViOWFjXHVjNzU4IFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJmNVx1Yzc3NCBcdWI5ZTRcdWM2YjAgXHVjZWU0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgMSwwMDAsMDAwLDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+KDI4OCwgMjg5KSA9IDEsICgyODgsIDI5MCkgPSA5LCAoMjg4LCAyOTEpID0gOCwgKDI4OSwgMjkwKSA9IDEwLCAoMjg5LCAyOTEpID0gOSwgKDI5MCwgMjkxKSA9IDEuIFx1YWMwMSBcdWMzMGRcdWM3NDQgXHViNDUwIFx1YmM4OFx1YzUyOSBcdWIzNTRcdWQ1NThcdWJhNzQgMiAqICgxICsgOSArIDggKyAxMCArIDkgKyAxKSA9IDc2LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6Ijk2MjkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQQVJPVkkiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byBpbnRlZ2VycyBpcyBkZWZpbmVkIGFzIHRoZSBzdW0gb2YgdGhlIGFic29sdXRlIHJlc3VsdCBvZiBzdWJ0cmFjdGluZyB0aGVpciBkaWdpdHMuIEZvciBleGFtcGxlLCB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgbnVtYmVycyA0NTYxIGFuZCAzMjc4IGlzIHw0ICZuZGFzaDsgM3wgKyB8NSAtIDJ8ICsgfDYgLSA3fCArIHwxIC0gOHwgPSAxMi4gSWYgb25lIG9mIHRoZSBudW1iZXJzIGNvbnNpc3RzIG9mIGZld2VyIGRpZ2l0cyB0aGFuIHRoZSBvdGhlciwgd2UgZmlsbCBpdCB3aXRoIGxlYWRpbmcgemVyb2VzLiBUaGVyZWZvcmUsIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBudW1iZXJzIDMyIGFuZCA1Njc4IGlzIHwwIC0gNXwgKyB8MCAtIDZ8ICsgfDMgLSA3fCArIHwyIC0gOHwgPSAyMS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0d28gaW50ZWdlcnMgQSBhbmQgQi4gQ2FsY3VsYXRlIHRoZSBzdW0gb2YgZGlzdGFuY2VzIGJldHdlZW4gZWFjaCBwYWlyIG9mIG51bWJlcnMgYmVsb25naW5nIGluIHRoZSBpbnRlcnZhbCBbQSwgQl0hJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBBLCBCICgxICZsZTsgQSAmbGU7IEIgJmxlOyAxMDxzdXA+NTAwMDA8XC9zdXA+KS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBudW1iZXIgZnJvbSB0aGUgdGV4dC4gR2l2ZW4gdGhhdCB0aGUgbnVtYmVyIGNvdWxkIGJlIGV4dHJlbWVseSBsYXJnZSwgb3V0cHV0IGFuc3dlciBtb2R1bG8gMSAwMDAgMDAwIDAwNy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIGRpc3RhbmNlcyBhcmUsIHJlc3BlY3RpdmVseSwgKDI4OCwgMjg5KSA9IDEsICgyODgsIDI5MCkgPSA5LCAoMjg4LCAyOTEpID0gOCwgKDI4OSwgMjkwKSA9IDEwLCAoMjg5LCAyOTEpID0gOSwgKDI5MCwgMjkxKSA9IDEuIEVhY2ggb2YgdGhlbSBjb3VudHMgdHdpY2UsIHdoaWNoIGlzIGluIHRvdGFsIDIgKiAoMSArIDkgKyA4ICsgMTAgKyA5ICsxKSA9IDc2LiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5UaGUgZGlzdGFuY2VzIGFyZSwgcmVzcGVjdGl2ZWx5LCAoMjg4LCAyODkpID0gMSwgKDI4OCwgMjkwKSA9IDksICgyODgsIDI5MSkgPSA4LCAoMjg5LCAyOTApID0gMTAsICgyODksIDI5MSkgPSA5LCAoMjkwLCAyOTEpID0gMS4gRWFjaCBvZiB0aGVtIGNvdW50cyB0d2ljZSwgd2hpY2ggaXMgaW4gdG90YWwgMiAqICgxICsgOSArIDggKyAxMCArIDkgKzEpID0gNzYuPFwvcD5cclxuIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #3 5번