D - Don't worry. Be Together Editorial /

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

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 の範囲が異なっている。
あるテストデータセットに含まれているテストデータ全てに対して正しい解を出力できると、それ以外のテストデータセットで不正解を出力しても以下のように部分点が与えられる。
  • part1 ( 40 点) : modulo=1,000,000,007、-1,000,000≦x_i,\ y_i≦1,000,000
  • part2 ( 30 点) : 1≦modulo≦1,000,000,007、-100≦x_i,\ y_i≦100
  • part3 ( 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