006 - わいわい (Y-y)

時間制限 8 秒 / メモリ制限 256 MB / 得点 100 / x 0 /


TLE
8sec
MLE
256MB
得点
100

問題

二次元平面上の 4 点 (Pi, Pj, Pk, Pl) について, 次のすべての条件を満たすとき, これらは Y 字 であるという. なお, 以下の説明では XnPn の X 座標, YnPn の Y 座標を表す.

  1. Xi < Xj かつ Yi < Yj.
  2. Xj < Xk かつ Yj < Yk < Yj + (Xk - Xj).
  3. Xj < Xl < Xj + (Yl - Yj) かつ Yj < Yl.

二次元平面上に N 個の点が与えられたとき, 平面上の Y 字の個数を 1000000007 で割ったあまりを求めよ.

入力

入力は M + 1 行からなる.
1 行目には 2 つの整数 N, M, A, B ( 1 ≤ N ≤ 100000, 0 ≤ M ≤ min(N, 1000), 1 ≤ A, B ≤ 109 ) が空白を区切りとして書かれている.
1 + i (1 ≤ iM) 行目には, 整数 XiYi (-109Xi, Yi ≤ 109) が空白を区切りとして書かれている. これは i 番目の点の X 座標および Y 座標の値を表している.
残りの N - M 個の点は, 以下の C++ 言語のコードを用いて作られる.

unsigned int r(){ 
	static unsigned int  x = 123456789,
	                     y = 362436069,
	                     z = 521288629,
	                     w = A;
	unsigned int t = (x ^ (x << 11)); 
	x = y; y = z; z = w;
	
	return (w = (w ^ (w >> 19) ^ (t ^ (t >> 8)))); 
}

void generate(int X[], int Y[])
{
    for (int i = M + 1; i <= N; i++){
        X[i] = r() % (2 * B + 1); X[i] -= B;
        Y[i] = r() % (2 * B + 1); Y[i] -= B;
    }
}

ここで, unsigned int 型は 32 ビット符号なし整数を表現できる型とし, int 型は 32 ビットの符号付き整数を表現できる型である.

出力

1 行に, 平面上の Y 字の個数を 1000000007 で割ったあまりを求めよ.

入出力例

入力例 1

12 2 893 15
-14 -9
0 1

出力例 1

8

入出力例 1 の 12 個の点の座標は以下のようになる :
(-14, -9), (0, 1), (-1, -15), (1, 2), (4, -6), (10, 5), (6, 6), (-11, -6), (-14, -7), (4, -11), (-3, 15), (7, -13).

この入力例では, 次の 8 つの点の組
(P1, P8, P2, P11), (P1, P8, P4, P11), (P1, P8, P6, P11), (P1, P8, P7, P11), (P9, P8, P2, P11), (P9, P8, P4, P11), (P9, P8, P6, P11), (P9, P8, P7, P11)
が Y 字を構成している.

入力例 2

52 0 41592627 1000000000

出力例 2

4568

入出力例 2 の最初の 10 個の点の座標は以下のようになる :
(683709195, -523773722), (-548167861, 169658628), (-564639697, -722129819), (-352632156, 679634347), (858639724, -673351832),
(252229649, 343817880), (556729437, -75294251), (643666477, 538005726), (-803284659, -412822891), (-831170606, 577935986).

入力例 3

3141 5 926 535
89 -79
-323 84
626 433
-83 -279
-5028 -8419

出力例 3

574575671