← 返回题目列表

AtCoder · abc265_e

H. 扭曲

中文机器翻译题面 查看原题

分数: 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