AT_ndpc2026_m 数字

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) $

The input is given from standard input in the following format: > $ N $ $ S $

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

### Sample Explanation 1 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`