问题描述

小k位于二维平面的原点。他将重复进行$N$次空间跃迁。每次跃迁时，他会选择以下一种移动方式：

• 从当前坐标$(x,y)$移动到$(x+A,y+B)$
• 从当前坐标$(x,y)$移动到$(x+C,y+D)$
• 从当前坐标$(x,y)$移动到$(x+E,y+F)$ 平面上有$M$个障碍点$(X_1,Y_1),\ldots,(X_M,Y_M)$；他不能跃迁到这些坐标。 经过$N$次跃迁后，可能的路径有多少条？请将结果对$998244353$取模后输出。

约束条件

• $1 \leq N \leq 300$
• $0 \leq M \leq 10^5$
• $-10^9 \leq A,B,C,D,E,F \leq 10^9$
• $(A,B)$、$(C,D)$和$(E,F)$互不相同。
• $-10^9 \leq X_i,Y_i \leq 10^9$
• $(X_i,Y_i)\neq(0,0)$
• $(X_i,Y_i)$互不相同。
• 输入中的所有值均为整数。

输入

输入通过标准输入给出，格式如下：

$NM$ $ABCDEF$ $X_1 Y_1$ $X_2 Y_2$ $\vdots$ $X_M Y_M$

输出

输出答案。

样例输入1

2 2
1 1 1 2 1 3
1 2
2 2

样例输出1

5

以下是可能的5条路径：

• $(0,0)\to(1,1)\to(2,3)$
• $(0,0)\to(1,1)\to(2,4)$
• $(0,0)\to(1,3)\to(2,4)$
• $(0,0)\to(1,3)\to(2,5)$
• $(0,0)\to(1,3)\to(2,6)$

样例输入2

10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

样例输出2

0

样例输入3

300 0
0 0 1 0 0 1

样例输出3

292172978