AT_ndpc2026_m.Numeral

You are given a string $S$ of length $2^N$ consisting of characters 1, 2, $\dots$, 9.

For each non-negative integer $n$ such that $0 \leq n \leq 2^N - 1$, define $f(n)$ as follows:

• List all non-negative integers $i$ such that $n \ \mathrm{OR} \ i = n$, and sort them in increasing order. Let them be $i_1, i_2, \dots, i_k$. Here, $\mathrm{OR}$ denotes the bitwise OR operation.
• Let $T$ be the string formed by taking the $(i_1+1)$-th, $(i_2+1)$-th, $\dots$, $(i_k+1)$-th characters of $S$ in this order.
• Interpret $T$ as a decimal integer, and let its value be $X$. Then define $f(n) = X \bmod 998244353$.

Compute all values $f(0), f(1), \dots, f(2^N - 1)$, and output the value of the following expression. Here, $\mathrm{XOR}$ denotes the bitwise exclusive OR operation.

$\displaystyle \sum_{n=0}^{2^N-1} \left(f(n) \ \mathrm{XOR} \ n\right)$

给定一个长度为 $2^N$ 的字符串 $S$，其字符仅由 1、2、$\dots$、9 组成。

对每个满足 $0 \leq n \leq 2^N - 1$ 的非负整数 $n$，定义函数 $f(n)$ 如下：

• 列出所有满足 $n \ \mathrm{OR} \ i = n$ 的非负整数 $i$，并将它们按升序排列，记为 $i_1, i_2, \dots, i_k$。其中 $\mathrm{OR}$ 表示按位或（bitwise OR）运算。
• 构造字符串 $T$，其字符依次为 $S$ 的第 $(i_1+1)$ 个、第 $(i_2+1)$ 个、$\dots$、第 $(i_k+1)$ 个字符。
• 将 $T$ 解释为一个十进制整数，记其值为 $X$；然后定义 $f(n) = X \bmod 998244353$。

请计算所有 $f(0), f(1), \dots, f(2^N - 1)$ 的值，并输出下列表达式的值。其中 $\mathrm{XOR}$ 表示按位异或（bitwise exclusive OR）运算。

$$\displaystyle \sum_{n=0}^{2^N-1} \left(f(n) \ \mathrm{XOR} \ n\right)$$

The input is given from standard input in the following format:

$N$
$S$

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

$N$
$S$

Print $\displaystyle \sum_{n=0}^{2^N-1} \left(f(n) \ \mathrm{XOR} \ n\right)$.

输出 $\displaystyle \sum_{n=0}^{2^N-1} \left(f(n) \ \mathrm{XOR} \ n\right)$。

Sample 1 Explanation:
For all $n$ such that $0 \leq n \leq 2^N-1$, the values of $f(n)$ are:

• When $n=0$, $f(n) = 1$
• When $n=1$, $f(n) = 12$
• When $n=2$, $f(n) = 13$
• When $n=3$, $f(n) = 1234$

Therefore, output $(1 \ \mathrm{XOR} \ 0) + (12 \ \mathrm{XOR} \ 1) + (13 \ \mathrm{XOR} \ 2) + (1234 \ \mathrm{XOR} \ 3) = 1 + 13 + 15 + 1233 = 1262$.

Constraints

• $1 \leq N \leq 22$
• $S$ is a string of length $2^N$ consisting of 1, 2, $\dots$, 9

样例 1 解释：
对于所有满足 $0 \leq n \leq 2^N-1$ 的 $n$，函数 $f(n)$ 的取值如下：

• 当 $n=0$ 时，$f(n) = 1$
• 当 $n=1$ 时，$f(n) = 12$
• 当 $n=2$ 时，$f(n) = 13$
• 当 $n=3$ 时，$f(n) = 1234$

因此，输出结果为 $(1 \ \mathrm{XOR} \ 0) + (12 \ \mathrm{XOR} \ 1) + (13 \ \mathrm{XOR} \ 2) + (1234 \ \mathrm{XOR} \ 3) = 1 + 13 + 15 + 1233 = 1262$。

限制条件

• $1 \leq N \leq 22$
• $S$ 是一个长度为 $2^N$ 的字符串，仅由字符 1、2、$\dots$、9 组成