$n$ 個の非ゼロの数字からなる文字列があります。任意の隣り合う 2 つの数字の間に、文字 $+$（プラス）または $\cdot$（乗算）を高々 1 つ挿入することで式を作ることができます。例えば、文字列 231 からは次の 9 個の式を作ることができます：

$231$, $23 + 1$, $23 \cdot 1$, $2 + 31$, $2 \cdot 31$, $2 + 3 + 1$, $2 + 3 \cdot 1$, $2 \cdot 3 + 1$, $2 \cdot 3 \cdot 1$.

これらの式を通常の演算順序に従って評価し、すべての値の総和を計算します。上の例では、次のようになります：

$$231 + 24 + 23 + 33 + 62 + 6 + 5 + 7 + 6 = 397$$

上記の総和を $10^9 + 7$ で割った余りを求めてください。

入力

入力の 1 行目には、文字列の長さを表す 1 つの整数 $n$（$1 \le n \le 10^6$）が与えられます。

2 行目には、数字 1–9 からなる長さ $n$ の文字列が与えられます。

出力

すべての式の値の総和を $10^9 + 7$ で割った余りを表す 1 つの整数を出力してください。

入出力例

入力例 1

3
231

出力例 1

397