ADASUM  Ada and Expenses
Ada the Ladybug has just returned from her trips. She noted all her expenses. Sadly, she only had a small piece of paper so she had to keep it in a compressed form. The compressed form is just a very long number. To restore the expenses, simply sum all contigous subsequences of the number. Since this number might be pretty big, you only have to output it modulo 10^{9}+7 (1000000007).
Can you help her to restore the number?
Input
The first and the only line of input containts the compressed sequence of digits ([0..9]): 1 ≤ s ≤ 2*10^{6}
Output
Print the sum of all contigous subsequences
Example Input
123
Example Output
164
Example Input 2
001
Example Output 2
3
Example Input 3
105004400
Example Output 3
127807548
Example Input 4
4774
Example Output 4
6245
Example Input 5
4369383968
Example Output 5
353343059
Example Input 6
447723168365033648256648424988
Example Output 6
42233771
hide comments
attiw:
20171109 05:07:29
simple 68 lines o(n) solution. 

nadstratosfer:
20170930 05:58:31
Just when I thought I figured out why my Python solution TLE's, still TLE. O(n) with seemingly nothing to optimize further. Any hints, morass? 

shubham_001:
20170912 13:41:31
@Blue.Mary oops i forgot that !, many thanks, got AC


[Rampage] Blue.Mary:
20170912 11:32:43
@shubham_001: your solution is not O(n), but O(nlogn), since it executes O(n) time explonent modulo, which has complexity O(logn) per operation. 

shubham_001:
20170912 11:22:34
@morass mine O(n) giving TLE my solution: https://ideone.com/******** Last edit: 20170912 11:43:21 

kunal9724kg:
20170907 20:00:03
@morass thanks :) 

morass:
20170906 18:31:53
@kunal9724kg: Good day to you,


kunal9724kg:
20170906 18:09:01
I am constantly getting wa on test case 15 any hint on what might be there in test case 15?? 

morass:
20170831 18:34:03
@sultania23: Good day to you,


morass:
20170831 18:32:34
@wisfaq: Thanks  edited ^_^ 
Added by:  Morass 
Date:  20170831 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 