AT_abc265_e [ABC265E] Warp

题目描述

高桥君位于二维平面上的原点。
接下来，高桥君将进行 $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$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

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

输出 #1

5

输入输出样例 #2

输入 #2

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

输出 #2

0

输入输出样例 #3

输入 #3

300 0
0 0 1 0 0 1

输出 #3

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)$ 两两不同
• 输入中的所有数均为整数

样例解释 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)$

由 ChatGPT 4.1 翻译