11444: ABC379 - E - Sum of All Substrings
[Creator : ]
Description
You are given a string $S$ of length $N$ consisting of digits from `1` through `9`.
For each pair of integers $(i,j) \ (1\leq i\leq j\leq N)$, define $f(i, j)$ as the value obtained by interpreting the substring of $S$ from the $i$-th through the $j$-th character as a decimal integer. Find $\displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i, j)$.
For each pair of integers $(i,j) \ (1\leq i\leq j\leq N)$, define $f(i, j)$ as the value obtained by interpreting the substring of $S$ from the $i$-th through the $j$-th character as a decimal integer. Find $\displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i, j)$.
Input
The input is given from Standard Input in the following format:
```
$N$
$S$
```
```
$N$
$S$
```
Output
Print the answer.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $N$ is an integer.
- $S$ is a string of length $N$ consisting of digits from `1` through `9`.
- $N$ is an integer.
- $S$ is a string of length $N$ consisting of digits from `1` through `9`.
Sample 1 Input
3
379
Sample 1 Output
514
The answer is $f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 3 + 37 + 379 + 7 + 79 + 9 = 514$.
Sample 2 Input
30
314159265358979323846264338327
Sample 2 Output
369673254065355789035427227741