Бинарные последовательности

Описание задачи

Будем называть последовательность бинарной, если каждый её элемент равен $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