题目描述

给定一个长度为 $2^N$ 的字符串 $S$，其中每个字符都是 1 到 9 之间的数字。

对于每个满足 $0\le n\le 2^N-1$ 的非负整数 $n$，按以下方式定义 $f(n)$：

1. 枚举所有满足$$n\mathbin{\mathrm{OR}}i=n$$ 的非负整数 $i$，并按升序排列为 $i_1,i_2,\ldots,i_k$。其中 $\mathrm{OR}$ 表示按位或。
2. 按顺序取出 $S$ 的第 $i_1+1,i_2+1,\ldots,i_k+1$ 个字符，拼接成字符串 $T$。
3. 将 $T$ 看作一个十进制整数，记其值为 $X$，并定义$$f(n)=X\bmod 998244353.$$

计算所有 $f(0),f(1),\ldots,f(2^N-1)$，并输出

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

其中 $\mathrm{XOR}$ 表示按位异或。最终的求和结果不需要取模。

限制条件

• $1\le N\le 22$
• $S$ 是长度为 $2^N$、仅由字符 1 到 9 组成的字符串。

输入

N
S

输出

输出

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

样例输入 1

2
1234

样例输出 1

1262

各个 $n$ 对应的值为：

• $f(0)=1$；
• $f(1)=12$；
• $f(2)=13$；
• $f(3)=1234$。

因此

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

样例输入 2

4
6415986517946482

样例输出 2

790534415