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
bomberking: 2024-10-06 00:56:52

why the is the solution to the first sample is 164
[Simes]: 1+2+3+12+23+123 = 164

Last edit: 2024-10-06 17:27:58
slothsphereoj: 2024-03-07 10:15:36

Simple observations lead to a code using MOD add, MOD minus and MOD multiplication.
Can be non-intuitive for faster solutions tho.

wrzoboo: 2018-06-18 15:40:00

i figured out solution using following method:
for input with length = z each digit = y take it's position = x
'1'*z = 111...111 (amount of ones equal to z)
answer = sum (y*(('1'*(z-x))*x)%1000000007
i still get TLE
is that still considered too high complexity? i create one operation for each digit in sequence
i notice only one AC in python3 with 7s, does a better algorithm exist? i tried many python optimization techniques already :(

Last edit: 2018-06-18 15:55:38
attiw: 2017-11-09 05:07:29

simple 6-8 lines o(n) solution.

nadstratosfer: 2017-09-30 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: 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: https://ideone.com/********

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!


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