Read problems statements in Mandarin Chinese and Russian as well.
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.
The only line of the input contains a single integer N without leading zeros.
Output the answer to the problem on the first line.
- 1 ≤ N ≤ 10100
Input: 7 Output: 84
|Tags||cook49, dynamic-programming, medium-hard, witua|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions