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<sstream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define fr(i,c) for(__typeof(c.begin()) i=c.begin();i!=c.end();i++)
#define pb push_back
#define mp make_pair
#define all(c) c.begin(),c.end()
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;
const int inf=(int)1e9;
const double EPS=1e-9, INF=1e12;

const int mod=(int)1e9+7;
int n,c,s,t;
ll C[2002][2002];
int m,in[2002];
vector<vi> e;

bool v[2002];
void rec(int c){
	v[c]=1;
	rep(i,e[c].size())if(!v[e[c][i]])rec(e[c][i]);
}
bool hasloop(){
	rep(i,n)if(in[i]==0&&!v[i])rec(i);
	rep(i,n)if(!v[i])return 1;
	return 0;
}

int cld[2002];
int reccld(int c){
	if(cld[c]>=0)return cld[c];
	cld[c]=1;
	rep(i,e[c].size())cld[c]+=reccld(e[c][i]);
	return cld[c];
}
ll T[2002];
ll recT(int c){
	ll &res=T[c];
	if(res>=0)return res;
	res=1;
	int n=cld[c]-1;
	rep(i,e[c].size()){
		res=res*recT(e[c][i])%mod;
		res=res*C[n][cld[e[c][i]]]%mod;
		n-=cld[e[c][i]];
	}
	return res;
}
ll dp[2002][2002],sum[2002][2002];

int main(){
	rep(i,2002)rep(j,i+1)C[i][j]=i==0||i==j?1ll:(C[i-1][j-1]+C[i-1][j])%mod;
	
	cin>>n>>c>>s>>t;
	e.resize(++n);
	rep(i,c){
		int a,b; cin>>a>>b;
		e[b].pb(a);
		in[a]++;
	}
	if(hasloop()){
		cout<<0<<endl; return 0;
	}
	for(int i=1;i<n;i++)if(in[i]==0)e[0].pb(i);
	t=n-t;
	
	static int prev[2002];
	rep(i,n)prev[i]=-1;
	queue<int> q; q.push(0);
	while(!q.empty()){
		int c=q.front(); q.pop();
		if(c==s)break;
		rep(i,e[c].size())q.push(e[c][i]), prev[e[c][i]]=c;
	}
	vi path;
	for(int c=s;c>=0;c=prev[c])path.pb(c);
	reverse(all(path));
	m=path.size();
	path.pb(n+1); T[n+1]=1;
	
	rep(i,n)cld[i]=T[i]=-1;
	rep(i,n)if(cld[i]<0)reccld(i);
	rep(i,n)if(T[i]<0)recT(i);
	
	rep(i,m){
		ll mul=1; int x=cld[path[i]]-cld[path[i+1]]-1;
		rep(j,e[path[i]].size())if(e[path[i]][j]!=path[i+1]){
			mul=mul*T[e[path[i]][j]]%mod*C[x][cld[e[path[i]][j]]]%mod;
			x-=cld[e[path[i]][j]];
		}
		rep(j,n+1)if(j>=i&&n-cld[path[i+1]]-1-j>=0){
			ll tmp=i&&j?sum[i-1][j-1]:1;
			tmp=tmp*C[n-cld[path[i+1]]-1-j][cld[path[i]]-cld[path[i+1]]-1]%mod;
			tmp=tmp*mul%mod;
			dp[i][j]=tmp;
			sum[i][j]=((j?sum[i][j-1]:0)+dp[i][j])%mod;
		}
	}
	cout<<dp[m-1][t]<<endl;
	
	return 0;
}