题目描述

$2$ 次元平面の原点に高橋君がいます。
高橋君はこれから、ワープを $N$ 回繰り返します。各ワープでは、以下の $3$ つのうちいずれか $1$ つを行います。

• 現在いる座標 $(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$

输出格式

答えを出力せよ。

题目大意

题目描述

ZK 现在在一个二维平面。他现在会进行 $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)$ ，这些点 ZK 是无法停留或经过的。

问 $N$ 次传送一共会有多少种路径？输出答案对 $998244353$ 取模。

输入描述

第一行两个整数 $N,M\;(1\le N \le 300, 0\le M \le 10^5)$。

第二行六个整数 $A,B,C,D,E,F\;(-10^9 \le A,B,C,D,E,F \le 10^9)$，保证无重复的二元对。

接下来 $M$ 行，每行两个整数 $X_i, Y_i\;(-10^9\le X_i,Y_i\le 10^9)$。保证 $(X_i,Y_i)\ne (0,0)$ 且无重复二元对。

输出描述

输出一行一个数字代表答案。

样例 1 解释

• $(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 2
1 1 1 2 1 3
1 2
2 2

5

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\ \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)$ は相異なる
• 入力に含まれる値は全て整数である

Sample Explanation 1

以下の $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)$