Sometimes it is not easy to come to an agreement in a bargain. Right now Sasha and Vova can’t come to an agreement: Sasha names a price as high as possible, then Vova wants to remove as many digits from the price as possible. In more details, Sasha names some integer price nn, Vova removes a non-empty substring of (consecutive) digits from the price, the remaining digits close the gap, and the resulting integer is the price.
For example, is Sasha names 12131211213121, Vova can remove the substring 13121312, and the result is 121121.
It is allowed for result to contain leading zeros. If Vova removes all digits, the price is considered to be 00.
Sasha wants to come up with some constraints so that Vova can’t just remove all digits, but he needs some arguments supporting the constraints. To start with, he wants to compute the sum of all possible resulting prices after Vova’s move.
Help Sasha to compute this sum. Since the answer can be very large, print it modulo 109+710^9+7.

Input

The first and only line contains a single integer nn (1≤n<10105)(1≤n<10^{10^5}).

Output

In the only line print the required sum modulo 109+710^9+7.

Examples

input

1
107

output

1
42

input

1
100500100500

output

1
428101984

Note

Consider the first example.
Vova can choose to remove 1,0,7,10,07,or1071, 0, 7, 10, 07, or 107. The results are 07,17,10,7,1,007, 17, 10, 7, 1, 0. Their sum is 4242.

Translation

给一个正整数 nn，可以选择 nn 上连续的位将之取出，于是 nn 就成了新的数。求所有操作剩下的数的和。

Idea

如果去掉的连续位在 nn 的头部或 nn 的尾部，可 O(n)O(n) 统计贡献。
若去掉的连续位在 nn 的中部，首先预处理出数组 valival_i，表示 nn 从 1 i1~i 位表示的数字。然后枚举去掉的连续位数的左右边界 ll 和 rr，那么 l+1∼r−1l+1\sim r-1 位的数字是被去掉的。首先枚举右边界 rr，再枚举左边界 ll，那么新的数字就是 vall×10r+numval_{l}\times 10^r+num，其中 numnum 是 r∼len(n)r\sim \mathrm{len}(n) 表示的数字。对于一个固定的右边界 rr，枚举左边界时，首先计算去掉 r−1r-1 位的数字，再计算去掉 r−2∼r−1r-2\sim r-1 位的数字，……，最后计算去掉 2∼r−12\sim r-1 位的数字；因此 ll 的取值是 [1,r−2][1,r-2]，产生的贡献是 10r×∑l=1r−2vall+(r−2)×num10^r\times\sum\limits_{l=1}^{r-2}val_l+(r-2)\times num。只需要处理 valival_i 的前缀和，也可以在 O(n)O(n) 时间内统计去掉中部连续位数的贡献。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1422C
Date: 10/6/2020
Description: Count, Dynamic Programming
*******************************************************************/
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=100006;
const int mod=1000000007;
char n[N];
ll val[N];
int main(){
	cin>>(n+1);
	int i,len=strlen(n+1);
	ll ans=0;
	for(i=1;i<=len;i++){
		val[i]=val[i-1]*10%mod+int(n[i]-'0');
		val[i]%=mod;
	}
	for(i=1;i<=len;i++){
		//前缀和
		val[i]+=val[i-1];
		val[i]%=mod;
	}
	ll power=1;
	ll num=0;
	for(i=len;i>=3;i--){
		//枚举右边界
		num+=power*int(n[i]-'0')%mod;
		num%=mod;
		ans+=num*(i-2)+(power*10)%mod*val[i-2]%mod;
		ans%=mod;
		power*=10;
		power%=mod;
	}
	num=0;
	power=1;
	for(i=len;i>=2;i--){
		//去掉头部
		num+=int(n[i]-'0')*power%mod;
		num%=mod;
		ans+=num;
		ans%=mod;
		power*=10;
		power%=mod;
	}
	num=0;
	for(i=1;i<=len-1;i++){
		//去掉尾部
		num=num*10+int(n[i]-'0')%mod;
		num%=mod;
		ans+=num;
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}