E - Warp 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

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 で割ったあまりを求めてください。

制約

  • 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

Score : 500 points

Problem Statement

Takahashi is at the origin of a two-dimensional plane.
Takahashi will repeat teleporting N times. In each teleportation, he makes one of the following moves:

  • Move from the current coordinates (x,y) to (x+A,y+B)
  • Move from the current coordinates (x,y) to (x+C,y+D)
  • Move from the current coordinates (x,y) to (x+E,y+F)

There are obstacles on M points (X_1,Y_1),\ldots,(X_M,Y_M) on the plane; he cannot teleport to these coordinates.

How many paths are there resulting from the N teleportations? Find the count modulo 998244353.

Constraints

  • 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), and (E,F) are distinct.
  • -10^9 \leq X_i,Y_i \leq 10^9
  • (X_i,Y_i)\neq(0,0)
  • (X_i,Y_i) are distinct.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A B C D E F
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

Output

Print the answer.

Sample Input 1

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

Sample Output 1

5

The following 5 paths are possible:

  • (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)

Sample Input 2

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

Sample Output 2

0

Sample Input 3

300 0
0 0 1 0 0 1

Sample Output 3

292172978