P4996 Gugugu

Xiao F is a student who is good at “pigeoning” (putting things off). He often delays tasks until the last day, which makes some of his days very rushed. For example, time goes back to November 3, 2018. Xiao F looks at his to-do list: 1. Watch iG win the championship. 2. Fix the problems from the monthly contest. Although Xiao F often goes “gugugu”, he is also very efficient when he works: in one step, he can finish any **non-empty subset** of the remaining tasks. For example, right now he can choose one of the following: 1. Watch iG win the championship. 2. Fix the monthly contest problems. 3. Watch the iG live stream while fixing the problems. Of course, the match is so exciting that Xiao F goes to watch it. However, when the golden rain falls and iG lifts the trophy, Xiao F suddenly feels guilty—the problems are not fixed yet. So, Xiao F feels a bit of remorse. Xiao F notices that he always feels remorse in certain situations. Every time he checks his task list to decide the next tasks, if he has done some tasks but has not done some other tasks, then he will feel a certain amount of remorse. For example, no matter whether he watched the match today or not, as long as he has not finished fixing the monthly contest problems, he will feel $1$ point of remorse when choosing tasks. After Xiao F finishes all tasks, the remorse value for that day equals the sum of the remorse values at each time he chooses tasks. A too-high remorse value makes Xiao F uneasy. Now, Xiao F tells you he still has $n$ tasks, and tells you that in one of $m$ situations $\mathrm{state}_i$, Xiao F will feel $a_i$ points of remorse. Please help compute the sum of the remorse values over all possible ways for Xiao F to finish all tasks on that day. Since the answer may be very large, you only need to output the answer modulo $998244353$.

The first line contains two integers $n, m$, meaning there are $n$ tasks, and among $m$ situations Xiao F will generate a remorse value. The next $m$ lines each contain a $0$-$1$ string $\mathrm{state}_i$ of length $n$ and an integer remorse value $a_i$. $\mathrm{state}_{i, j}$ is $0/1$, meaning that the $j$-th task is not done / already done at that time. Please refer to the samples and the sample explanation for details.

Output one integer in one line, representing the sum of the remorse values over all possible ways to finish all tasks on that day, modulo $998244353$.

#### Sample 1 Explanation: In the $0$-$1$ string, the first digit indicates whether Xiao F watched the match, and the second digit indicates whether Xiao F fixed the problems. We use $\varnothing$ to denote that Xiao F did nothing, $A$ to denote that Xiao F watched the match, and $B$ to denote that Xiao F fixed the problems. Then the ways that will produce guilt are as follows: $\varnothing: 1$ $\{A\}:1$ Then all possible choices are: $\varnothing\rightarrow\{A\}\rightarrow\{A,B\}:2$ $\varnothing\rightarrow\{B\}\rightarrow\{A,B\}:1$ $\varnothing\rightarrow\{A,B\}:1$ So the answer is $2 + 1 + 1 = 4$. #### Constraints It is guaranteed that all given $\mathrm{state}_i$ are pairwise distinct. For all testdata, $1 \leq n \leq 20$, $1 \leq m \leq \min(2 ^ n, 10 ^ 5), 1 \leq a_i \leq 10 ^ 5$. | Case | $n$ | | :------:|:------: | |1|$1$| |2|$2$| |3|$3$| |4|$10$| |5|$12$| |6|$14$| |7|$16$| |8|$18$| |9|$19$| |10|$20$| Translated by ChatGPT 5