ADASUM - Ada and Expenses

no tags 

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?


The first and the only line of input containts the compressed sequence of digits ([0..9]): 1 ≤ |s| ≤ 2*106


Print the sum of all contigous subsequences

Example Input


Example Output


Example Input 2


Example Output 2


Example Input 3


Example Output 3


Example Input 4


Example Output 4


Example Input 5


Example Output 5


Example Input 6


Example Output 6


hide comments
shubham_001: 2017-09-12 13:41:31

@Blue.Mary oops i forgot that !, many thanks, got AC
as you have looked at my solution can u tell my how do I optimize it? spacetime wise

Last edit: 2017-09-12 13:43:44
[Rampage] Blue.Mary: 2017-09-12 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: 2017-09-12 11:22:34

@morass mine O(n) giving TLE my solution:********

Last edit: 2017-09-12 11:43:21
kunal9724kg: 2017-09-07 20:00:03

@morass thanks :)

morass: 2017-09-06 18:31:53

@kunal9724kg: Good day to you,

Firstly your program gets WA on second test-case, not on 15th.

Secondly, I've added additional samble input (hope I copied it correctly) on which your program seems to fail.

Good Luck & Have Nice Day!

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"

Added by:Morass
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)