Binary Sequences

Problem Description

We call a sequence to be binary sequence, if each its element is $0$ or $1$.

There are $m$ conditions. The $i$-th condition is described by three integers $x_i$, $y_i$, and $a_i$.

Consider the first $x_i$ elements of the sequence. This condition is satisfied if exactly $y_i$ of them are equal to $1$. If it is satisfied, it adds $a_i$ to the total score.

For given integers $r$ and $b$, define $F(r,b)$ as the maximum total score among all binary sequences of size $n$ that has at most $r$ elements equal to $1$ and at most $b$ elements equal to .

Compute $\sum_{r=0}^{n} \sum_{b=n-r}^{n} F(r,b) \bmod 998244353.$

Input Format

The first line contains two integers $n$ and $m$ $(1 \le n \le 10^9, 1 \le m \le 2 \cdot 10^5)$.

The second line contains $m$ integers $x_1, x_2, \dots, x_m$ $$.

The third line contains $m$ integers $y_1, y_2, \dots, y_m$ .

The fourth line contains $m$ integers $a_1, a_2, \dots, a_m$ $$.

Output Format

Print one integer: the value

$\sum_{r=0}^{n} \sum_{b=n-r}^{n} F(r,b) \bmod 998244353.$

2
5 5
3 2 5 5 2
2 2 1 0 1
8 10 5 6 6
5 5
5 4 5 4 1
4 3 1 0 0
4 9 8 9 7

344
415