← 返回题目列表

AtCoder · arc012_4

D. 别担心。在一起

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

問題文

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≦N≦100,000) ,表示移动圈数的整数 T(1≦T≦100,000) 、正整数 modulo 用空格分隔。
  • 2 从行 N 字里行间 在 i+1(1≦i≦N) 行中, 一个整数,表示第i 个人的坐标。 x_i,\ y_i 用空格分隔。

部分点

测试数据包括以下内容: 3 包含在其中一种类型的测试数据集中,并且每个数据集中包含的测试数据是如下给出的整数。 modulo,\ x_i,\ y_i 范围不同。
如果某个测试数据集中包含的所有测试数据都能输出正确答案,则即使其他测试数据集输出错误答案,也会按如下方式给出部分分数。
  • 第 1 部分 ( 40 点) : modulo=1,000,000,007、-1,000,000≦x_i,\ y_i≦1,000,000
  • 第 2 部分 ( 30 点) : 1≦modulo≦1,000,000,007、-100≦x_i,\ y_i≦100
  • 第 3 部分 ( 30 点) : 1≦modulo≦1,000,000,007、-1,000,000≦x_i,\ y_i≦1,000,000

出力

只是 T 找出回合后大家有多少种方式在原点集合。 输出modulo后的余数。
如果无论你做什么都无法让所有人同时聚集到原点, 请输出0 。
输出应发送到标准输出,并在末尾添加换行符。

入力例 1

2 2 1000000007
1 1
-1 -1

出力例 1

4
  • x 右侧正坐标,y 坐标为正的方向为顶部。
  • 2 两人在转弯时到达原点的方式如下。 4 如下。
    • 1该人向下向右移动,2该人的眼睛向上并向左移动。
    • 1该人向下向右移动,2人的眼睛向左移动,然后向顶部移动。
    • 1该人向右移动,然后向底部移动。2该人的眼睛向上并向左移动。
    • 1该人向右移动,然后向底部移动。2人的眼睛向左移动,然后向顶部移动。

入力例 2

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

出力例 2

1
  • 由于除了直接指向原点的模式之外,没有其他模式,所以答案是 1 如下。

入力例 3

1 6 10
0 0

出力例 3

0
  • 6 如何从原点转弯返回原点 400 方法有很多,所以 除以 10 后的余数 0 。

入力例 4

3 7 12345
2 3
0 1
-2 -1

出力例 4

11415