Hamako Online Judge

TLE
8sec

MLE
256MB

得点
5

問題

二次元平面上の 4 点 (P_i, P_j, P_k, P_l) について, 次のすべての条件を満たすとき, これらは Y 字 であるという. なお, 以下の説明では X_n で P_n の X 座標, Y_n で P_n の Y 座標を表す.

X_i < X_j かつ Y_i < Y_j.
X_j < X_k かつ Y_j < Y_k < Y_j + (X_k - X_j).
X_j < X_l < X_j + (Y_l - Y_j) かつ Y_j < Y_l.

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

入力

入力は M + 1 行からなる.
1 行目には 2 つの整数 N, M, A, B ( 1 ≤ N ≤ 100000, 0 ≤ M ≤ min(N, 1000), 1 ≤ A, B ≤ 10⁹ ) が空白を区切りとして書かれている.
1 + i (1 ≤ i ≤ M) 行目には, 整数 X_i と Y_i (-10⁹ ≤ X_i, Y_i ≤ 10⁹) が空白を区切りとして書かれている. これは 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

入出力例 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 つの点の組
(P₁, P₈, P₂, P₁₁), (P₁, P₈, P₄, P₁₁), (P₁, P₈, P₆, P₁₁), (P₁, P₈, P₇, P₁₁), (P₉, P₈, P₂, P₁₁), (P₉, P₈, P₄, P₁₁), (P₉, P₈, P₆, P₁₁), (P₉, P₈, P₇, P₁₁)
が Y 字を構成している.

入力例 2

52 0 41592627 1000000000

出力例 2

入出力例 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

0256 - わいわい (Y-y)

問題

入力