AT_ndpc2026_m 数字

`1`, `2`, $ \dots $ , `9` からなる長さ $ 2^N $ の文字列 $ S $ が与えられます。 $ 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} $ はビットごとの論理和を意味する。 - $ S $ の $ i_1+1 $ 文字目, $ i_2+1 $ 文字目, $ \dots $ , $ i_k+1 $ 文字目をこの順に並べてできる文字列を $ T $ とする。 - $ T $ を $ 10 $ 進整数とみなした時の値を $ X $ とする。そして、 $ f(n) = X \bmod 998244353 $ とする。 $ f(0), f(1), \dots, f(2^N-1) $ を全て計算してください。そして、次式の値を出力してください。ここで $ \mathrm{XOR} $ はビットごとの排他的論理和を意味します。 $ \displaystyle \sum_{n=0}^{2^N-1} \left(f(n) \ \mathrm{XOR} \ n\right) $

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $

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

### Sample Explanation 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 $ を出力してください。 ### Constraints - $ 1 \leq N \leq 22 $ - $ S $ は `1`, `2`, $ \dots $ , `9` からなる長さ $ 2^N $ の文字列