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 翻译