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 109+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*106
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