#include <bits/stdc++.h>
using namespace std;
const int N = 2100;
const int M = 200010;
const int p = 1000000007;
int r[N], c[N], n, m, k, S, id[N];
long long f[N][22], C[N][N], jie[M], rev[M], two[22], P, Q;
bool bad[N], con[N][N];
long long fast(long long x, int k) {
  long long ans = 1;
  for (; k; k >>= 1) {
    if (k & 1) ans = ans * x % p;
    x = x * x % p;
  }
  return ans;
}
void init() {
  int i, j;
  for (jie[0] = 1, i = 1; i < M; ++i) jie[i] = jie[i - 1] * i % p;
  rev[M - 1] = fast(jie[M - 1], p - 2);
  for (i = M - 2; i >= 0; --i) rev[i] = rev[i + 1] * (i + 1) % p;
  for (two[0] = 1, i = 1; i < 22; ++i) two[i] = (two[i - 1] << 1) % p;
}
inline bool cmp(int a, int b) { return r[a] + c[a] < r[b] + c[b]; }
inline void calc(int x, int y) {
  if (r[y] >= r[x] && c[y] >= c[x])
    con[x][y] = 1;
  else
    return;
  C[x][y] = jie[r[y] + c[y] - r[x] - c[x]];
  C[x][y] = C[x][y] * rev[r[y] - r[x]] % p * rev[c[y] - c[x]] % p;
}
int main() {
  ios ::sync_with_stdio(false);
  int i, j, x, y, tmp, ii, jj;
  cin >> n >> m >> k >> S;
  init();
  for (i = 1; i <= k; ++i) cin >> r[i] >> c[i], id[i] = i;
  sort(id + 1, id + 1 + k, cmp);
  int s = 1, t = k;
  if (r[id[1]] != 1 || c[id[1]] != 1) id[s = 0] = 0, r[s] = c[s] = 1;
  if (r[id[k]] != n || c[id[k]] != m) id[t = k + 1] = t, r[t] = n, c[t] = m;
  for (i = 1; i <= k; ++i) bad[i] = 1;
  for (i = s; i < t; ++i) {
    for (j = i + 1; j <= t; ++j) calc(id[i], id[j]);
  }
  if (bad[t])
    f[t][1] = 1;
  else
    f[t][0] = 1;
  for (i = t - 1; i >= s; --i) {
    x = id[i];
    tmp = bad[x];
    for (j = 0; j <= 20; ++j) {
      if (j == 0 && bad[x]) continue;
      f[i][j] = C[x][id[t]];
      for (ii = i + 1; ii <= t; ++ii) {
        y = id[ii];
        if (con[x][y]) {
          f[i][j] -= C[x][y] * f[ii][j + 1 - tmp] % p;
          (f[i][j] += p) %= p;
        }
      }
      for (jj = j - 1; jj >= 0; --jj) ((f[i][j] -= f[i][jj]) += p) %= p;
    }
  }
  for (tmp = C[id[s]][id[t]], i = 0; i <= 20; ++i) {
    x = S / two[i] + (S % two[i] != 0);
    (P += f[s][i] * 1LL * x % p) %= p;
    ((tmp -= f[s][i]) += p) %= p;
  }
  (P += tmp) %= p, Q = C[id[s]][id[t]];
  cout << (P * fast(Q, p - 2) % p) << endl;
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

Unfortunately, the formal description of the task turned out to be too long, so here is the legend.

Research rover finally reached the surface of Mars and is ready to complete its mission. Unfortunately, due to the mistake in the navigation system design, the rover is located in the wrong place.

The rover will operate on the grid consisting of n rows and m columns. We will define as (r, c) the cell located in the row r and column c. From each cell the rover is able to move to any cell that share a side with the current one.

The rover is currently located at cell (1, 1) and has to move to the cell (n, m). It will randomly follow some shortest path between these two cells. Each possible way is chosen equiprobably.

The cargo section of the rover contains the battery required to conduct the research. Initially, the battery charge is equal to s units of energy.

Some of the cells contain anomaly. Each time the rover gets to the cell with anomaly, the battery looses half of its charge rounded down. Formally, if the charge was equal to x before the rover gets to the cell with anomaly, the charge will change to <image>.

While the rover picks a random shortest path to proceed, compute the expected value of the battery charge after it reaches cell (n, m). If the cells (1, 1) and (n, m) contain anomaly, they also affect the charge of the battery.

Input

The first line of the input contains four integers n, m, k and s (1 ≤ n, m ≤ 100 000, 0 ≤ k ≤ 2000, 1 ≤ s ≤ 1 000 000) — the number of rows and columns of the field, the number of cells with anomaly and the initial charge of the battery respectively.

The follow k lines containing two integers ri and ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m) — coordinates of the cells, containing anomaly. It's guaranteed that each cell appears in this list no more than once.

Output

The answer can always be represented as an irreducible fraction <image>. Print the only integer P·Q - 1 modulo 109 + 7.

Examples

Input

3 3 2 11
2 1
2 3


Output

333333342


Input

4 5 3 17
1 2
3 3
4 1


Output

514285727


Input

1 6 2 15
1 1
1 5


Output

4

Note

In the first sample, the rover picks one of the following six routes:

  1. <image>, after passing cell (2, 3) charge is equal to 6. 
  2. <image>, after passing cell (2, 3) charge is equal to 6. 
  3. <image>, charge remains unchanged and equals 11. 
  4. <image>, after passing cells (2, 1) and (2, 3) charge equals 6 and then 3. 
  5. <image>, after passing cell (2, 1) charge is equal to 6. 
  6. <image>, after passing cell (2, 1) charge is equal to 6. 



Expected value of the battery charge is calculated by the following formula:

<image>.

Thus P = 19, and Q = 3.

3 - 1 modulo 109 + 7 equals 333333336.

19·333333336 = 333333342 (mod 109 + 7)

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2100;
const int M = 200010;
const int p = 1000000007;
int r[N], c[N], n, m, k, S, id[N];
long long f[N][22], C[N][N], jie[M], rev[M], two[22], P, Q;
bool bad[N], con[N][N];
long long fast(long long x, int k) {
  long long ans = 1;
  for (; k; k >>= 1) {
    if (k & 1) ans = ans * x % p;
    x = x * x % p;
  }
  return ans;
}
void init() {
  int i, j;
  for (jie[0] = 1, i = 1; i < M; ++i) jie[i] = jie[i - 1] * i % p;
  rev[M - 1] = fast(jie[M - 1], p - 2);
  for (i = M - 2; i >= 0; --i) rev[i] = rev[i + 1] * (i + 1) % p;
  for (two[0] = 1, i = 1; i < 22; ++i) two[i] = (two[i - 1] << 1) % p;
}
inline bool cmp(int a, int b) { return r[a] + c[a] < r[b] + c[b]; }
inline void calc(int x, int y) {
  if (r[y] >= r[x] && c[y] >= c[x])
    con[x][y] = 1;
  else
    return;
  C[x][y] = jie[r[y] + c[y] - r[x] - c[x]];
  C[x][y] = C[x][y] * rev[r[y] - r[x]] % p * rev[c[y] - c[x]] % p;
}
int main() {
  ios ::sync_with_stdio(false);
  int i, j, x, y, tmp, ii, jj;
  cin >> n >> m >> k >> S;
  init();
  for (i = 1; i <= k; ++i) cin >> r[i] >> c[i], id[i] = i;
  sort(id + 1, id + 1 + k, cmp);
  int s = 1, t = k;
  if (r[id[1]] != 1 || c[id[1]] != 1) id[s = 0] = 0, r[s] = c[s] = 1;
  if (r[id[k]] != n || c[id[k]] != m) id[t = k + 1] = t, r[t] = n, c[t] = m;
  for (i = 1; i <= k; ++i) bad[i] = 1;
  for (i = s; i < t; ++i) {
    for (j = i + 1; j <= t; ++j) calc(id[i], id[j]);
  }
  if (bad[t])
    f[t][1] = 1;
  else
    f[t][0] = 1;
  for (i = t - 1; i >= s; --i) {
    x = id[i];
    tmp = bad[x];
    for (j = 0; j <= 20; ++j) {
      if (j == 0 && bad[x]) continue;
      f[i][j] = C[x][id[t]];
      for (ii = i + 1; ii <= t; ++ii) {
        y = id[ii];
        if (con[x][y]) {
          f[i][j] -= C[x][y] * f[ii][j + 1 - tmp] % p;
          (f[i][j] += p) %= p;
        }
      }
      for (jj = j - 1; jj >= 0; --jj) ((f[i][j] -= f[i][jj]) += p) %= p;
    }
  }
  for (tmp = C[id[s]][id[t]], i = 0; i <= 20; ++i) {
    x = S / two[i] + (S % two[i] != 0);
    (P += f[s][i] * 1LL * x % p) %= p;
    ((tmp -= f[s][i]) += p) %= p;
  }
  (P += tmp) %= p, Q = C[id[s]][id[t]];
  cout << (P * fast(Q, p - 2) % p) << endl;
  return 0;
}

```