Problem Description

Xiao F is a student who excels at procrastination, often leaving tasks until the last day, resulting in some days being extremely hectic for him.

For example, let's time-travel back to November 3, 2018. Xiao F looks at his to-do list:

1. Watch iG win the championship;
2. Fix the issues with the monthly competition problems.

Although Xiao F frequently procrastinates, he is also very efficient at completing tasks. He can complete any non-empty subset of the remaining tasks at once. For instance, he can choose from the following options:

1. Watch iG win the championship;
2. Fix the issues with the monthly competition problems;
3. Watch the live broadcast of iG winning while fixing the problems.

However, the match is too exciting, so Xiao F decides to watch the game.

But when the golden rain falls and iG lifts the trophy, Xiao F suddenly feels guilty—he hasn't fixed the problems yet! Consequently, he experiences a sense of regret.

Xiao F notices that he always feels regret under certain circumstances. Whenever he checks his to-do list to decide on the next task, if he has done some tasks but not others, he will experience a certain amount of regret. For example, regardless of whether he has watched the game or not, as long as he hasn't fixed the monthly competition problems, he will feel $1$ point of regret when choosing the next task. The total regret value for Xiao F on that day is the sum of the regrets he experiences each time he makes a choice.

Excessive regret makes Xiao F feel uneasy. Now, Xiao F tells you that he has $n$ tasks left and that under $m$ different conditions $\mathrm{state}_i$, he will experience $a_i$ points of regret. Please help calculate the sum of the regret values for all possible ways Xiao F can complete all tasks on that day, modulo $998244353$.

Input Format

The first line of input contains two integers $n, m$, indicating that there are $n$ tasks and $m$ conditions under which Xiao F will experience regret.

The next $m$ lines each contain a $0-1$ string $\mathrm{state}_i$ of length $n$ and an integer $a_i$. $\mathrm{state}_{i, j}$ being $0/1$ indicates that the $j$-th task has not been done / has been done.

Refer to the sample input and explanation for details.

Output Format

Output a single integer, which is the sum of the regret values for all possible ways Xiao F can complete the tasks on that day, modulo $998244353$.

Sample Input and Output

Sample Input #1

2 2
00 1
10 1

Sample Output #1

4

Sample Input #2

3 4
000 16
001 9
110 4
111 1

Sample Output #2

260

Notes

Sample 1 Explanation:

The first digit in the $0-1$ string indicates whether Xiao F has watched the game, and the second digit indicates whether he has fixed the problems.

We use $\varnothing$ to denote that Xiao F has done nothing, $A$ to denote that he has watched the game, and $B$ to denote that he has fixed the problems. The ways that will cause regret are as follows:

$\varnothing: 1$
$\{A\}: 1$

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

Data Range

It is guaranteed that all $\mathrm{state}_i$ are distinct.

For all data, $1 \leq n \leq 20$, $1 \leq m \leq \min(2^n, 10^5)$, $1 \leq a_i \leq 10^5$.

见题面 Input 部分

见题面 Output 部分