问题

有 $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$ 个人所在的坐标 $(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$ 种方法让两个人到达原点：

  • 第一个人先向下移动，然后向右移动；第二个人先向上移动，然后向左移动；
  • 第一个人先向下移动，然后向右移动；第二个人先向左移动，然后向上移动；
  • 第一个人先向右移动，然后向下移动；第二个人先向上移动，然后向左移动；
  • 第一个人先向右移动，然后向下移动；第二个人先向左移动，然后向上移动；

输入示例 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