Problem 30: Sum of Substrings

Problem Statement: Given a numeric string, compute the sum of all possible substrings of the string taken as numbers. Since the answer can be very large, output it modulo 10^9+7.

Input

A single line containing a numeric string.

Output

Print the sum of all substrings modulo 10^9+7.

Examples


Input:
16

Output:
23

Solution Explanation

Method 1: Use dynamic programming to compute the contribution of each digit to all substrings it appears in. Method 2: Use a mathematical formula that calculates the sum of substrings by considering the position of each digit, which leads to an O(n) solution.

Solution in C++


#include 
#include 
using namespace std;

const long long MOD = 1000000007;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    long long n = s.size();
    long long sum = 0, f = 1;
    long long res = 0;
    // f[i] stores contribution factor for digit at index i from right end
    // We use reverse iteration.
    for (int i = n - 1; i >= 0; i--) {
        int digit = s[i] - '0';
        sum = (sum + (long long)(i + 1) * f) % MOD;
        res = (res + digit * sum) % MOD;
        f = (f * 10 + 1) % MOD;
    }
    cout << res % MOD << "
";
    return 0;
}