const int Mod = ?;

int powM(int x, int y = Mod-2) {
	int ret = 1;
	while (y) {
		if (y&1) ret = 1ll*ret*x%Mod;
		x = 1ll*x*x%Mod, y >>= 1;
	} return ret;
}

int fac[N], ifac[N];
void init() {
	fac[1] = ifac[1] = fac[0] = ifac[0] = 1;
	for (int i = 2; i < Mod; ++i) fac[i] = 1ll*fac[i-1]*i%Mod;
	ifac[Mod-1] = powM(fac[Mod-1]);
	for (int i = Mod-2; i; --i) ifac[i] = 1ll*ifac[i+1]*(i+1)%Mod;
}
int C(int x, int y) {
	if (x < y) return 0;
	if (!x || !y || x == y) return 1;
	return 1ll*fac[x]*ifac[x-y]%Mod*ifac[y]%Mod;
}
int luc(int x, int y) {
	if (x < y) return 0;
	if (!x || !y || x == y) return 1;
	return 1ll*C(x%Mod, y%Mod)*luc(x/Mod, y/Mod)%Mod;
}

int sum[N<<2], taga[N<<2], tagm[N<<2], a[N];
void pushup(int &x, int y, int z) {x = plu(y, z);}
void build(int now, int L, int R) {
	tagm[now] = 1;
	if (L == R) {
		sum[now] = a[L];
		return ;
	}
	segc;
	build(lc, L, mid), build(rc, mid+1, R);
	pushup(sum[now], sum[lc], sum[rc]);
}
void pushdown(int now, int L, int R) {
	segc;
	sum[lc] = plu(mul(sum[lc], tagm[now]), mul(taga[now], mid-L+1));
	sum[rc] = plu(mul(sum[rc], tagm[now]), mul(taga[now], R-mid));
	tagm[lc] = mul(tagm[lc], tagm[now]);
	tagm[rc] = mul(tagm[rc], tagm[now]);
	taga[lc] = plu(mul(taga[lc], tagm[now]), taga[now]);
	taga[rc] = plu(mul(taga[rc], tagm[now]), taga[now]);
	taga[now] = 0, tagm[now] = 1;
}
void modifya(int now, int L, int R, int ql, int qr, ll val) {
	if (ql <= L && R <= qr) {
		sum[now] += val*(R-L+1);
		taga[now] += val;
		return ;
	}
	segc;
	pushdown(now, L, R);
	if (ql <= mid) modifya(lc, L, mid, ql, qr, val);
	if (qr > mid) modifya(rc, mid+1, R, ql, qr, val);
	pushup(sum[now], sum[lc], sum[rc]);
}
void modifym(int now, int L, int R, int ql, int qr, ll val) {
	if (ql <= L && R <= qr) {
		sum[now] = mul(sum[now], val);
		taga[now] = mul(taga[now], val);
		tagm[now] = mul(tagm[now], val);
		return ;
	}
	segc;
	pushdown(now, L, R);
	if (ql <= mid) modifym(lc, L, mid, ql, qr, val);
	if (qr > mid) modifym(rc, mid+1, R, ql, qr, val);
	pushup(sum[now], sum[lc], sum[rc]);
}
ll ask(int now, int L, int R, int ql, int qr) {
	if (ql <= L && R <= qr) return sum[now];
	segc; int ret = 0;
	pushdown(now, L, R);
	if (ql <= mid) ret = plu(ret, ask(lc, L, mid, ql, qr));
	if (qr > mid) ret = plu(ret, ask(rc, mid+1, R, ql, qr));
	return ret;
}

int ans[N<<2];
double mx[N<<2];
int query(int now, int L, int R, double Lim) {
	if (mx[now] <= Lim) return 0;
	if (L == R) return 1;
	segc;
	if (mx[lc] <= Lim) return query(rc, mid+1, R, Lim);
	return query(lc, L, mid, Lim)+ans[now]-ans[lc];
}
void update(int now, int L, int R, int pos, double val) {
	if (L == R) {
		ans[now] = 1;
		mx[now] = val;
		return ;
	}
	segc;
	if (pos <= mid) update(lc, L, mid, pos, val);
	else update(rc, mid+1, R, pos, val);
	mx[now] = max(mx[lc], mx[rc]);
	ans[now] = ans[lc]+query(rc, mid+1, R, mx[lc]);
}

int dis[N];
bool vis[N];
void dij(int S) {
	for (int i = 1; i <= n; ++i) dis[i] = Inf;
	dis[S] = 0;
	priority_queue<pair<int, int> > q;
	q.push(mp(0, S));
	while (!q.empty()) {
		int x = q.top().second; q.pop();
		if (vis[x]) continue ;
		vis[x] = true;
		for (int i = head[x]; i; i = e[i].next) {
			int y = e[i].to;
			if (dis[y] > dis[x]+e[i].w) {
				dis[y] = dis[x]+e[i].w;
				if (!vis[y]) q.push(mp(-dis[y], y));
			}
		}
	}
}

int f[N<<1];
void kru() {
	sort(e+1, e+1+m, cmp);
	for (int i = 1; i <= 2*n; ++i) fa[i] = i;
	int ncnt = n;
	for (int i = 1; i <= m; ++i) {
		int fu = find(e[i].u), fv = find(e[i].to);
		if (fu == fv) continue ;
		fa[fu] = fa[fv] = ++ncnt;
		add(ncnt, fu), add(fu, ncnt);
		add(ncnt, fv), add(fv, ncnt);
		val[cnt] = e[i].w;
	}
}

#define ll long long
#define segc int mid = L+R>>1, lc = now<<1, rc = lc|1
int plu(int x, int y) {return (1ll*x+y)%Mod};
int mul(int x, int y) {return 1ll*x*y%Mod};