숫자 $1, 2, \dots, 9$로 이루어진 길이 $N$인 문자열 $S$가 주어집니다.
총 $\frac{N(N+1)}{2}$개의 블록으로 이루어진 삼각형 피라미드를 생각해 봅시다.
피라미드는 위에서 아래로 $1, 2, \dots, N$번까지 번호가 매겨진 $N$개의 층으로 나뉩니다. $i$번째 층($1 \le i \le N$)에는 왼쪽에서 오른쪽으로 한 줄로 나열된 $i$개의 블록이 있습니다. 각 블록에는 문자열이 하나씩 적혀 있습니다. $i$번째 층에서 왼쪽에서 $j$번째 블록($1 \le j \le i$)에 적힌 문자열을 $C_{i,j}$라고 합시다.
문자열 $C_{i,j}$는 다음 조건을 만족합니다:
- 만약 $i = N$이면, $C_{i,j}$는 $S$의 $j$번째 문자로 이루어진 길이 $1$인 문자열입니다.
- 만약 $1 \le i < N$이면, $C_{i,j}$는 $C_{i+1,j}$와 $C_{i+1,j+1}$을 이 순서대로 이어 붙인 문자열입니다.
$C_{1,1}$을 십진법 정수로 해석했을 때, 그 값을 $998244353$으로 나눈 나머지를 구하세요.
입력
입력은 다음 형식으로 주어집니다:
N S
- $N$은 정수이다.
- $1 \le N \le 2 \times 10^5$.
- $S$는 숫자 $1, 2, \dots, 9$로 이루어진 길이 $N$인 문자열이다.
출력
답을 출력합니다.
예제
입력 1
4 8192
출력 1
81191992
입력 2
1 5
출력 2
5
입력 3
14 11123455678999
출력 3
913063116
노트
첫 번째 예제에서 $S = 8192$입니다. 규칙에 따라 피라미드를 만들면 $C_{1,1} = 81191992$를 얻습니다.
두 번째 예제에서 $S = 5$입니다. 피라미드는 단 하나의 블록으로 이루어져 있으며, $C_{1,1} = 5$입니다.