Printing Types

Suppose you write every natural number from 1 through N. Each digit needed to write a number counts as one printing type.

For N = 10, you write 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10, so 11 printing types are needed in total.

Find the number of printing types needed to write all natural numbers not greater than N.

The first line contains a natural number N.

• 1 <= N <= 2,000,000,000

Print the number of required printing types modulo 1,234,567.