$0$이 아닌 $n$개의 숫자로 이루어진 문자열이 있습니다. 인접한 두 숫자 사이에 문자 $+$ (더하기) 또는 $\cdot$ (곱하기) 중 최대 하나를 삽입하여 수식을 만들 수 있습니다. 예를 들어, 문자열 231로부터 아홉 개의 수식을 만들 수 있습니다:

$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$로 나눈 나머지를 구하십시오.

입력

입력의 첫째 줄에는 문자열의 길이를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

둘째 줄에는 숫자 1–9로 이루어진 길이 $n$의 문자열이 주어집니다.

출력

모든 수식의 합을 $10^9 + 7$로 나눈 나머지를 나타내는 정수 하나를 출력합니다.

예제

예제 입력 1

3
231

예제 출력 1

397