103794: [Atcoder]ABC379 E - Sum of All Substrings

Problem Statement

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)$.

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.

Input

The input is given from Standard Input in the following format:

$N$
$S$

Output

Print the answer.

Sample Input 1

3
379

Sample Output 1

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 Input 2

30
314159265358979323846264338327

Sample Output 2

369673254065355789035427227741

问题陈述

给定一个由数字1到9组成的长度为$N$的字符串$S$。

对于每一对整数$(i,j)\ (1\leq i\leq j\leq N)$，定义$f(i, j)$为将$S$中从第$i$个到第$j$个字符的子字符串解释为十进制整数所得到的值。求$\displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i, j)$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $N$是一个整数。
• $S$是由数字1到9组成的长度为$N$的字符串。

输入

输入从标准输入以下格式给出：

$N$
$S$

输出

打印答案。

样本输入1

3
379

样本输出1

514

答案是$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$。

样本输入2

30
314159265358979323846264338327

样本输出2

369673254065355789035427227741