Problem: Problem statement

Find the number of integer sequences $ X_1, X_2, ..., X_N $ that satisfy the following conditions.


1. For any integer $ i $ ($ 1 \ leq i \ leq N $), there exists $ j $ ($ 1 \ leq j \ leq N $) such that $ X_j = i $.
2. $ X_s = t $
3. $ X_ {a_i} <X_ {b_i} $ ($ 1 \ leq i \ leq C $)

Constraint

* $ 1 \ leq N \ leq 2000 $
* $ 0 \ leq C \ leq N $
* $ 1 \ leq s \ leq N $
* $ 1 \ leq t \ leq N $
* $ 1 \ leq a_i \ leq N $
* $ 1 \ leq b_i \ leq N $
* $ a_i \ neq b_i $
* $ i \ neq j $ then $ a_i \ neq a_j $



input

Input follows the following format. All given numbers are integers.


$ N $ $ C $ $ s $ $ t $
$ a_1 $ $ b_1 $
$ a_2 $ $ b_2 $
$ ... $
$ a_C $ $ b_C $

output

Divide the number of sequences that satisfy the condition by $ 10 ^ 9 + 7 $ and output the remainder on one row (it is easy to show that the number of sequences that satisfy the condition is at most finite).

Examples

Input

3 1 1 1
1 3


Output

2


Input

4 2 1 1
2 3
3 2


Output

0

Solution (in CPP):

Solution:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

const ll MOD = 1e+9 + 7;
ll combi[2020][2020];
vector<int> g[2020];
int parent[2020];
int memo[2020][2020];
int cnt[2020];
int cnt2[2020];
int sum[2020];
int n, c, s, t;

void dfs(int node) {
  ll c = 1;
  sum[node] = 1;
  FORIT(it, g[node]) {
    dfs(*it);
    sum[node] += sum[*it];
  }
  ll rest = sum[node] - 1;
  FORIT(it, g[node]) {
    c = c * cnt[*it] % MOD * combi[rest][sum[*it]] % MOD;
    rest -= sum[*it];
  }
  cnt[node] = c;
}

ll Cnt(int node, int left, int child) {
  int rest = n - left;
  if (cnt2[node] == -1) {
    ll ret = 1;
    int r = sum[node] - 1;
    if (node != child) { r -= sum[child]; }
    FORIT(it, g[node]) {
      if (*it == child) { continue; }
      ret = ret * cnt[*it] % MOD * combi[r][sum[*it]] % MOD;
      r -= sum[*it];
    }
    cnt2[node] = ret;
  }
  rest--;
  int r = sum[node] - 1;
  if (node != child) {
    rest -= sum[child];
    r -= sum[child];
  }
  if (rest < 0) { return 0; }
  return cnt2[node] * combi[rest][r] % MOD;
}

ll calc(int node, int left, int child) {
  if (left < 0) { return 0; }
  if (memo[node][left] != -1) { return memo[node][left]; }
  ll ret = Cnt(node, left, child);
  if (node != 0) {
    ret = (ret * calc(parent[node], left - 1, node)) % MOD;
  }
  if (node != child) {
    ret = (ret + calc(node, left - 1, child)) % MOD;
  }
  return memo[node][left] = ret;
}

int main() {
  MEMSET(combi, 0);
  combi[0][0] = 1;
  REP(i, 2010) REP(j, 2010) {
    combi[i + 1][j] = (combi[i + 1][j] + combi[i][j]) % MOD;
    combi[i + 1][j + 1] = (combi[i + 1][j + 1] + combi[i][j]) % MOD;
  }
  while (scanf("%d %d %d %d", &n, &c, &s, &t) > 0) {
    n++;
    t = n - t;
    MEMSET(parent, 0);
    MEMSET(memo, -1);
    MEMSET(cnt, -1);
    MEMSET(cnt2, -1);
    MEMSET(sum, 0);
    REP(i, 2020) { g[i].clear(); }
    REP(i, c) {
      int from, to;
      scanf("%d %d", &to, &from);
      g[from].push_back(to);
      parent[to] = from;
    }
    FOR(i, 1, n) {
      if (parent[i] == 0) { g[0].push_back(i); }
    }
    dfs(0);
    ll ans = 0;
    if (sum[0] == n) {
      ans = calc(s, t, s);
    }
    printf("%lld\n", ans);
  }
}