Counting of Digits

3

4 votes
Problem

You are given an integer N. For each pair of integers (L, R), where 1 ≤ L ≤ R ≤ N you can find the number of distinct digits that appear in the decimal representation of at least one of the numbers L L+1 ... R.

Find the sum of all that numbers. Since the answer can be large, output it modulo 1000000007.

INPUT

The only line of the input contains a single integer N without leading zeros.

OUTPUT

Output the answer to the problem on the first line.

CONSTRAINTS

1 ≤ N ≤ 10^100
Time Limit: 2
Memory Limit: 256
Source Limit:
Editor Image

?