问题描述

高橋在一个二维平面的原点。
高橋会重复进行 $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)$ 是不同的。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $A$ $B$ $C$ $D$ $E$ $F$ $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