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 contiguous 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 contains the compressed sequence of digits ([0..9]): 1 ≤ |s| ≤ 2*106

Output

Print the sum of all contiguous 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
kunal9724kg: 2017-09-06 18:09:01

I am constantly getting wa on test case 15 any hint on what might be there in test case 15??

morass: 2017-08-31 18:34:03

@sultania23: Good day to you,

sadly I don't understend Ruby.

Anyway actually none of your C/C++ codes are O(N) [all of them are O(N^2) - which causes the TLE]


Good luck
Have nice day

Hope you'll find the bug ^_^

morass: 2017-08-31 18:32:34

@wisfaq: Thanks - edited ^_^

sultania23: 2017-08-31 15:08:22

O(n) still tle.why?

wisfaq: 2017-08-31 14:08:22

I also think that you should replace "comprimed" with "compressed"

morass: 2017-08-31 11:34:26

@wisfaq: Thanx - I've modified it a little bit. Well by that I mean sequence of digits from 0 to 9 of length at most 2*10^6 ^_^

Good Luck!
Have nice day!

wisfaq: 2017-08-31 10:07:42

The first and the only line of input containts the comprimed sequence of digits [0..9] 1 ≤ |s1| ≤ 2*106 test-cases.
What is the function of "test cases" here?
Moreover what do you mean with: [0..9] 1 ≤ |s1| ≤ 2*10^6

Last edit: 2017-08-31 10:09:17
wisfaq: 2017-08-31 10:06:17

What is a continuous subsequence?
Do you mean: contiguous subsequence?


Added by:Morass
Date:2017-08-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All