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 <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long int64;

const int MAX_N = 2000 + 1;
const int64 MOD = (int64)(1e9 + 7);

int N, C, target, ord;

int parent[MAX_N+1];
vector<int> graph[MAX_N+1];

int V[MAX_N+1];
int S[MAX_N+1];
int64 T[MAX_N+1];

int64 dp[MAX_N+1][MAX_N+1];
bool visited[MAX_N + 1];
int64 comb[MAX_N+1][MAX_N+1];

void init(){
	scanf("%d%d%d%d", &N, &C, &target, &ord);
	ord = N - ord + 1;
	++N;
	parent[0] = -1;
	for(int i=0; i<C; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		parent[a] = b;
		graph[b].push_back(a);
	}

	for(int i=0; i<N; i++)if(parent[i] == 0){
		graph[0].push_back(i);
	}

	for(int i=0; i<=N; i++){
		comb[i][i] = comb[i][0] = 1;
		for(int j=1; j<i; j++){
			comb[i][j] = ( comb[i-1][j-1] + comb[i-1][j] ) % MOD;
		}
	}
}

void calc(int v){
	T[v] = S[v] = 1;
	for(int i=0; i<(int)graph[v].size(); ++i){
		const int u = graph[v][i];
		calc(u);
		S[v] += S[u];
	}

	int total = S[v] - 1;
	for(int i=0; i<(int)graph[v].size(); i++){
		const int u = graph[v][i];
		T[v] = T[v] * comb[total][S[u]] % MOD * T[u] % MOD;
		total -= S[u];
	}
}

int solve(){
	calc(0);
	if(S[0] != N){
		return 0;
	}

	const int dummy = N;
	S[dummy] = 0;
	parent[dummy] = target;

	int depth = 0;
	for(int v = target; v!=-1 ;V[depth++]=v, v=parent[v]);
	reverse(V, V+depth);
	V[depth] = dummy;

	for(int i=0; i<depth; i++){
		int cur = V[i], nxt = V[i+1], all = N - S[nxt];
		int64 sum = 0, prod = 1;
		int total = S[cur] - S[nxt] - 1;
		for(int j=0; j<(int)graph[cur].size(); j++){
			const int u = graph[cur][j];
			if(nxt != u){
				prod = prod * T[u] % MOD * comb[total][S[u]] % MOD;
				total -= S[u];
			}
		}
		if(i == 0){
			dp[0][0] = prod;
			continue;
		}
		for(int j=1; j<N; j++){
			sum = (sum + dp[i-1][j-1]) % MOD;
			int rem = all - j - 1, child = S[cur] - S[nxt] - 1;
			if(rem >= child && rem >= 0 && child >= 0){
				dp[i][j] = sum * comb[rem][child] % MOD * prod % MOD;
			}
		}
	}

	return (int)dp[depth-1][ord];
}

int main(){
	init();
	printf("%d\n", solve());

	return 0;
}