AT_arc012_4.[ARC012D] Don't worry. Be Together

有 $N$ 个人站在二维平面上的格点上。
每一回合，每个人都必须向上、下、左、右四个方向中的某一个方向恰好移动 $1$ 单位。
重复进行这个操作，要求在第 $T$ 回合结束时，所有人都能同时到达原点 $(0,0)$。
请输出所有人各自的移动方式的组合数对 $modulo$ 取余的结果。
如果无论如何都无法让所有人同时到达原点，则输出 $0$。
输入按以下格式从标准输入读入。

$N$ $T$ $modulo$ $x_1$ $y_1$ $x_2$ $y_2$ : : $x_N$ $y_N$

• 第 $1$ 行输入三个整数，分别表示人数 $N(1\leq N\leq 100,000)$，移动回合数 $T(1\leq T\leq 100,000)$，正整数 $modulo$，以空格分隔。
• 第 $2$ 行到第 $N+1$ 行的第 $i+1$ 行，输入第 $i$ 个人的坐标 $x_i,\ y_i$，以空格分隔。

测试数据包含以下三种数据集之一，每个数据集中的 $modulo,\ x_i,\ y_i$ 的取值范围不同。
如果你能对某一数据集中的所有测试数据输出正确答案，即使在其他数据集上输出错误，也会获得部分分数。

• part1（$40$ 分）：$modulo=1,000,000,007$，$-1,000,000\leq x_i,\ y_i\leq 1,000,000$
• part2（$30$ 分）：$1\leq modulo\leq 1,000,000,007$，$-100\leq x_i,\ y_i\leq 100$
• part3（$30$ 分）：$1\leq modulo\leq 1,000,000,007$，$-1,000,000\leq x_i,\ y_i\leq 1,000,000$

请输出恰好在 $T$ 回合后所有人都能到达原点的移动方式组合数对 $modulo$ 取余的结果。
如果无论如何都无法让所有人同时到达原点，则输出 $0$。
输出请在标准输出中给出，末尾需换行。

2 2 1000000007
1 1
-1 -1

4

• $x$ 坐标正方向为右，$y$ 坐标正方向为上。
• 在第 $2$ 回合，两个人到达原点的方法有以下 $4$ 种。
• 第 $1$ 个人依次向下、右移动，第 $2$ 个人依次向上、左移动。
• 第 $1$ 个人依次向下、右移动，第 $2$ 个人依次向左、上移动。
• 第 $1$ 个人依次向右、下移动，第 $2$ 个人依次向上、左移动。
• 第 $1$ 个人依次向右、下移动，第 $2$ 个人依次向左、上移动。

4 4 1000000007
0 4
4 0
-4 0
0 -4

1

• 每个人只能直线走向原点，没有其他方案，所以答案为 $1$。

1 6 10
0 0

0

• $6$ 回合内从原点回到原点的方法有 $400$ 种，$400$ 对 $10$ 取余为 $0$，所以输出 $0$。

3 7 12345
2 3
0 1
-2 -1

11415

第 $1$ 行输入三个整数 $N$、$T$、$modulo$，以空格分隔。
接下来 $N$ 行，每行输入两个整数 $x_i$、$y_i$，以空格分隔，表示第 $i$ 个人的初始坐标。

输出一个整数，表示所有人恰好在 $T$ 回合后同时到达原点的移动方式组合数对 $modulo$ 取余的结果。
如果无论如何都无法让所有人同时到达原点，则输出 $0$。
输出后请换行。

由 ChatGPT 4.1 翻译