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 10⁹+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*10⁶

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