Description：

给一个 $DAG$ 和另外一条边 $u\to v$ ，求树形图的方案数。

$1\leqslant n\leqslant 10^5$

Solution：

首先如果是一个 $DAG$ 的话答案就是： $$ \prod_{i=2}^n\mathrm{ind}[i] $$ 但是新多了一条边，这样做就可能回成环，假如说我们枚举了环上的点集为 $S$ ，那么 $S$ 上的点的入度选择情况是确定的，也就是我们应该减掉： $$ \sum_S\frac{\prod_{i=2}^n}{\prod_{i\in S}\mathrm{ind[i]}} $$ 换句话说我们应该减掉所有以 $v$ 开始以 $u$ 结束的边形成的路径上面那个值之和，因为图是 $DAG$ 所以直接做就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m,u,v;

#define MAXN 100010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

int ind[MAXN];

int sum = 1;

#define MOD 1000000007

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % MOD)if(b & 1)res = 1ll * res * a % MOD;

	return res;

}

int f[MAXN];

bool vis[MAXN];

void dfs(int k)

{

	if(vis[k])return;

	vis[k] = true;

	if(k == u)

	{

		f[k] = 1ll * sum * power(ind[k],MOD - 2) % MOD;

		return;

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dfs(e[i].to);

		f[k] = (f[k] + 1ll * f[e[i].to] * power(ind[k],MOD - 2) % MOD) % MOD;

	}

	return;

}

int main()

{

	scanf("%d%d%d%d",&n,&m,&u,&v);

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		a = rd();b = rd();

		add(a,b);++ind[b];

	}

	++ind[v];

	for(int i = 2;i <= n;++i)sum = 1ll * sum * ind[i] % MOD;

	if(v != 1)dfs(v);

	cout << (sum - f[v] + MOD) % MOD << endl;

	return 0;

}