← 返回题目列表

Codeforces · 57/E

E. 国际象棋

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

兔子布莱恩喜欢下棋。不久前,他与兔子斯蒂维争论说,骑士比国王更好。为了证明他的观点,他试图证明骑士速度非常快,但史蒂维不接受没有证据的陈述。他为布莱恩构建了一个无限的棋盘,并删除了几个方格以增加游戏的趣味性。 Brian 只需要计算一个骑士站在坐标为 (0, 0) 的方格上,在不超过 k 步的时间内可以到达多少个不同的棋盘方格。当然,被删除的方格是被禁止移动的。

Brian自己不太喜欢精确科学,也不熟悉编程,这就是为什么他很难超越已经开始解决问题的Stewie。帮助 Brian 比 Stewie 更快地解决问题。

输入

第一行包含两个整数 k 和 n (0 ≤ k ≤ 1018, 0 ≤ n ≤ 440),分别是骑士可以走的最大步数和删除的单元格数。然后接下来的 n 行,每行以 (xi, yi) 的形式给出删除的正方形的坐标(|xi| ≤ 10,|yi| ≤ 10)。所有数字均为整数,删除的方格不同,保证方格(0, 0)不被删除。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin (也可以使用 %I64d)。

输出

您必须将答案打印在一行上。由于它可能相当长,因此您应该以 1000000007 为模打印它。

示例

输入 #1

1 0

输出 #1

9

输入 #2

2 7
-1 2
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1

输出 #2

9