1951번 - 활자

문제

옛날에는 책을 만들 때, 한글자 한글자를 나눠서 활자를 만들어서 그걸 합쳐서 책을 만들었다고 한다. 예를 들면 가나다라는 글씨를 쓰기 위해서는 3개의 활자가 필요할 것이다. 그렇다고 할 때, N이하의 자연수를 활자로 표현하기 위해서는 몇 개의 활자가 필요한지 구하여라. 예를 들어 10이하의 자연수를 활자로 표현하려면 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0 이렇게 11개의 활자가 필요할 것이다.

입력

첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)이 주어진다.

출력

첫째 줄에 필요한 활자의 수를 1234567로 나눈 나머지를 출력한다.

제한

힌트