1141 : Reverse

Description

Bobo has an n digits decimal number D = d₁d₂…d_n (It may have leading zeros).

Let R(i, j) denotes number D with digits between the i-th position and j-th position reversed.

That is, R(i, j) = d₁…d_i − 1d_jd_j − 1…d_id_j + 1d_j + 2…d_n.

Bobo would like to find

$$ \sum_{i=1}^{n}\sum_{j=i}^{n}R(i,j) $$

modulo (10⁹ + 7).

Input

The input contains at most 30 sets. For each set:

The first line contains an integer n(1 ≤ n ≤ 10⁵).

The second line contains n digits d₁d₂…d_n(0 ≤ d_i ≤ 9).

Output

For each set, an integer denotes the result.

Sample

2
12
3
012
10
0123456789

45
369
733424314

Hint

Source

Author

ftiasch