Пайдарпаии дуӣ

Тавсифи масъала

Мо пайдарпаиро пайдарпаии дуӣ меномем, агар ҳар як элементи он $0$ ё $1$ бошад.

$m$ шарт мавҷуд аст. Шарти $i$-ум бо се адади бутун $x_i$, $y_i$ ва $a_i$ тавсиф мешавад.

Аввалин $x_i$ элементи пайдарпаиро баррасӣ кунед. Ин шарт иҷро мешавад, агар маҳз $y_i$-тои онҳо ба $1$ баробар бошанд. Агар шарт иҷро шавад, он ба холи умумӣ $a_i$ илова мекунад.

Барои ададҳои бутуни додашудаи $r$ ва $b$, $F(r,b)$-ро ҳамчун холи умумии максималӣ дар байни ҳамаи пайдарпаии дуии дарозии $n$ муайян мекунем, ки на бештар аз $r$ элементи баробар ба $1$ ва на бештар аз $b$ элементи баробар ба доранд.

Ҳисоб кунед $\sum_{r=0}^{n} \sum_{b=n-r}^{n} F(r,b) \bmod 998244353.$

Input Format

Сатри аввал ду адади бутуни $n$ ва $m$-ро дар бар мегирад $(1 \le n \le 10^9, 1 \le m \le 2 \cdot 10^5)$.

Сатри дуюм $m$ адади бутуни $x_1, x_2, \dots, x_m$-ро дар бар мегирад $$.

Сатри сеюм $m$ адади бутуни $y_1, y_2, \dots, y_m$-ро дар бар мегирад .

Сатри чорум $m$ адади бутуни $a_1, a_2, \dots, a_m$-ро дар бар мегирад $$.

Output Format

Як адади бутунро чоп кунед: қимати $\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