Warp

题目描述

Takahashi 位于二维平面的原点。
Takahashi 将重复进行 $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$

输出格式

输出答案。

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)$ 彼此互不相同。 输入中的所有值均为整数。下面的 $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)$

标签: AtCoder|abc265E

来源

AtCoder|abc265E