[ABC265E] Warp

### 题目描述 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)$。

[problemUrl]: https://atcoder.jp/contests/abc265/tasks/abc265_e $ 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 $

答えを出力せよ。

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