整数划分

题目描述

给定十进制表示下有 $N$ 位的正整数 $X$。$X$ 的任何一位数字都不是 $0$。

对 $\{1,2, \ldots, N-1\}$ 的子集 $S$,定义 $f(S)$ 如下。

将 $X$ 的十进制表示看作长度为 $N$ 的字符串,当且仅当 $i \in S$ 时在第 $i$ 个字符与第 $(i+1)$ 个字符之间切开,将其分解为 $|S| + 1$ 个字符串。

然后,将这 $|S| + 1$ 个字符串分别视为十进制表示的整数,设 $f(S)$ 为这 $|S| + 1$ 个整数的乘积。

$\{1,2, \ldots, N-1\}$ 的子集(包括空集)共有 $2^{N-1}$ 个,均可以作为 $S$。求所有这样的 $S$ 的 $f(S)$ 之和,对 $998244353$ 取模。

输入格式

输入按以下格式从标准输入给出:

$N$
$X$

输出格式

输出答案。

样例

3
234

418

对于 $S = \emptyset$,有 $f(S) = 234$。

对于 $S = \{1\}$,有 $f(S) = 2 \times 34 = 68$。

对于 $S = \{2\}$,有 $f(S) = 23 \times 4 = 92$。

对于 $S = \{1, 2\}$,有 $f(S) = 2 \times 3 \times 4 = 24$。

因此,应输出 $234 + 68 + 92 + 24 = 418$。

4
5915

17800

9
998244353

258280134

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $X$ 是十进制下 $N$ 位、且任何一位都不是 $0$ 的正整数。
• 输入中的所有值均为整数。