C. Bargain time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output 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 n, 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 1213121, Vova can remove the substring 1312, and the result is 121.
It is allowed for result to contain leading zeros. If Vova removes all digits, the price is considered to be 0.
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+7.
Input The first and only line contains a single integer n (1≤n<10105).
Output In the only line print the required sum modulo 109+7.
Examples inputCopy 107 outputCopy 42 inputCopy 100500100500 outputCopy 428101984 Note Consider the first example.
Vova can choose to remove 1, 0, 7, 10, 07, or 107. The results are 07, 17, 10, 7, 1, 0. Their sum is 42.
将这个数字分为三段，前m位，第x位和后n位，（m+n+1==string.length());，这样总和就转变为求后n位对第x位贡献与前m位对第x位贡献之和了。循环再求和一遍即可。 求后n位贡献的方法，观察可知，如果想让第x位作为个位，(n=1)那么后面只有0种选择，所以贡献和为1pow(10,0),如果想让第x位作为十位(n=2),贡献和为2pow（10，1）；以此类推可知后n位的总贡献和为tot+=i*fast(10,i-1)(1<=i<n)；这里fast是指快速幂。 求前m位贡献的方法 这里相当于在x位之前的高位删除子序列，因此不影响后n位的贡献和。因此枚举前m位删除i个字符的情况，最后可得前面m位的贡献和为（m+1)*m/2乘以后n位的贡献和。
