分数: 500 点
问题陈述
高桥位于二维平面的原点。
高桥将重复传送 N 次。 在每次传送中,他都会做出以下动作之一:
- 从当前坐标移动 (x,y) to (x+A,y+B)
- 从当前坐标移动 (x,y) to (x+C,y+D)
- 从当前坐标移动 (x,y) to (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