Sum of All Values

Given a string num consisting only of the digits 0-9. You may insert one '+' between any two adjacent characters; adjacent '+' signs are not allowed, and you may also insert none at all. Each way of inserting produces an expression, and each segment separated by '+' is evaluated as a decimal integer (leading zeros do not affect the value; for example, 05 has value 5). Find the sum of the values of all possible expressions, modulo 10^9+7.

输入格式

A single line containing the string num. 1≤|num|≤3×10^7, containing only the characters 0-9.

输出格式

Output one integer: the sum of the values of all expressions modulo 10^9+7.

样例 1

输入：

123

输出：

168

样例 2

输入：

105

输出：

132

样例 3

输入：

7

输出：

7

样例说明

Example 1: the expressions for "123" are 1+23=24, 12+3=15, 1+2+3=6, and 123=123, for a total of 168. Example 2: the expressions for "105" are 105, 1+05=6, 10+5=15, and 1+0+5=6, for a total of 132. Example 3: "7" has only one expression, with value 7.