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<iostream>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 2010;

//loop finding begin
vector<int> loopedge[N];
int loopvis[N];
bool loopFindingDfs(int u){
  if (loopvis[u] == 2)return false;
  if (loopvis[u] == 1)return true;
  loopvis[u]=1;
  rep(i,(int)loopedge[u].size()){
    if (loopFindingDfs(loopedge[u][i]))return true;
  }
  loopvis[u]=2;
  return false;
}
bool hasLoop(int n){
  rep(i,n)loopvis[i]=0;
  rep(i,n){
    if (loopvis[i] == 0 && loopFindingDfs(i))return true;
  }
  return false;
}
//loop finding end

/*
  brute force solver
  condition x[first] < x[second]
  x[s] = t
*/
//--------------------------------------------------
int bf(int n,vector<pair<int,int> > &cond,int s,int t){
  int x[n];
  int ret = 0;
  rep(i,n)x[i] = i + 1;
  do{
    if (x[s] != t)continue;
    rep(i,cond.size()){
      if (x[cond[i].first] > x[cond[i].second])goto end;
    }
    ret++;
  end:;
  }while(next_permutation(x,x+n));
  return ret;
}
//--------------------------------------------------

ll comb[N][N];
void precalc(){
  comb[0][0] = 1;
  REP(i,1,N){
    comb[i][0] = comb[i][i] = 1;
    REP(j,1,i)comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % mod;
  }
}

//solver
vector<int> edge[N];
int child[N];//子ノードの数
int req[N];//X[i]を子ノードとして持つなら、そのノードのインデックスを保持する。
int maxnum[N];//X[i]を子ノードとして持つとき、Xi未満の値を最大どのくらい持っていいのか
int reqnum;//X[i]以下のノードの数。
//子ノードの数を数え上げる。メモ化なし
int countChild(int now){
  int ret = 1;
  rep(i,(int)edge[now].size()){
    ret += countChild(edge[now][i]);
  }
  return child[now] = ret;
}

//X[i]以下のノードの数と、xi以下に遷移するノードの番号を記録しておく。
bool countReq(int now,const int s,bool childOfXs){
  req[now] = -1;
  bool ret = (now == s);
  rep(i,edge[now].size()){
    bool tmp = countReq(edge[now][i],s,childOfXs|(now == s));
    if (tmp)req[now] = i;
    ret |= tmp;
  }
  if (now == s)reqnum = child[now] -1;
  return ret;
}

//xs以下のノードが最大何個まで許容されるかを数える
int countXs(int now,int s){
  if (now == s)return maxnum[now] = child[now] - 1;
  if (req[now] == -1)return child[now];
  int ret = 0;
  maxnum[now] = 0;
  rep(i,edge[now].size()){
    int &next = edge[now][i];
    if (req[now] != i)maxnum[now] += child[next];
    else maxnum[now] += countXs(next,s);
  }
  return maxnum[now];
}

/*
  現在のノード、xs以下のノードの数
  xsを子ノードとして持たない場合はxs=0を代入してしまう
*/
ll dp[N][N];
int solveRec(int now,int xs,int s){
  if (req[now] == -1)xs = 0;
  ll &ret = dp[now][xs];
  if (ret != -1)return ret;
  ret = 1;
  int num = child[now]-1;
  //xsを子ノードとして持つノードから処理していく。
  if (req[now] != -1){
    ret = 0;
    int &next = edge[now][req[now]];
    REP(i,reqnum,maxnum[next]+1){
      if (xs < i)break;
      int larger = child[now] - xs -2;//tより大きい,child[now] -xs -(自分+t (1+1) )
      int konode = child[next]-1;//konode > xi
      konode -= i;
      if (konode > larger)continue;

      ll tmp = solveRec(next,i,s);
      tmp *= comb[xs][i];//xs以下のノードからi個えらぶ。
      tmp %= mod;
      tmp *= comb[larger][konode];//
      ret += tmp;
      ret %= mod;
    }
    num -= child[next];
  }
  rep(i,edge[now].size()){
    if (req[now] == i)continue;//このノードはもう処理したので無視する
    int & next = edge[now][i];
    ll tmp = solveRec(next,0,s);
    tmp *= comb[num][child[next]];
    tmp %= mod;
    num -= child[next];
    ret *= tmp;
    ret %= mod;
  }
  return ret;
}

int solve(int n,int s,int t){
  countChild(0);
  countReq(0,s,false);
  countXs(0,s);
  ll ret = solveRec(0,t-1,s);
  return ret;
}


int main(){
  precalc();
  int n,c,t,s;
  static bool hasParent[N];
  while(cin>>n>>c>>s>>t && n){
    vector<pair<int,int> > cond;
    rep(i,n){
      loopedge[i].clear();
    }
    rep(i,n+1){
      rep(j,n+1)dp[i][j] = -1;
      hasParent[i] = false;
      edge[i].clear();
      reqnum = 0;
    }
    rep(i,c){
      int a,b;
      cin>>a>>b;
      //擬似的な親としてx0を追加する。こいつは、ルートになっているすべてのノードより大きい必要があるぽよ。
      edge[b].push_back(a);
      hasParent[a] = true;
      a--;b--;
      cond.push_back(make_pair(a,b));
      loopedge[b].push_back(a);
    }
    n++;
    REP(i,1,n){
      if (!hasParent[i])edge[0].push_back(i);
    }
    //cout <<"DEBUGED ANSWER IS " << bf(n-1,cond,s-1,t) << endl;//debug
    //solver
    if (hasLoop(n)){cout << 0 << endl;continue;}
    cout << solve(n,s,t) << endl;
  }
  return 0;
}