传送

题目描述

Takahashi 位于二维平面上的原点。

Takahashi 将重复进行 $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$ 取模。

输入格式

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

$N$ $M$
$A$ $B$ $C$ $D$ $E$ $F$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_M$ $Y_M$

输出格式

输出答案。

样例

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

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)$

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

0

300 0
0 0 1 0 0 1

292172978

数据范围

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