Description：

甲乙各有 $k_1,k_2$ 个区间，每次随机从每个区间中挑出一个数求和，问 $S_1>S_2$ ， $S_1=S_2$ ， $S_1<S_2$ 概率。

$1\le k \le 8,1\le l,r\le 10^7$

Solution：

若 $S_1>S_2$ ，设甲选的数为 $R_i-x_i,x_i\in[0,R_i-L_i]$ ，乙选的数为 $L_i+y_i,y_i\in[0,R_i-L_i]$ ，于是 $\sum R_i-\sum x_i>\sum L_i+\sum y_i$ ，变形为 $\sum R_i-\sum L_i>\sum y_i+\sum x_i$ ， $\sum R_i-\sum L_i-1=\sum y_i+\sum x_i+k,k\in[0,+\infty)$ 。

这个方程每个未知量都有上限，求解的个数，可以容斥，设 $S(i)$ 表示至少有 $i$ 个未知量不满足条件的方案数，则 $\begin{align}ans=\sum_{i=0}^n(-1)^i\times S(i)\end{align}$ ，枚举每个未知数是否符合，如果他不符合，那么 $x_i>up_i$ ，即 $x_i-up_i-1\ge 0$ ，那就在等式右边减掉 $up_i+1$ 。于是又变成了一个有下界的方程，且一定有大于等于个不符合，每个未知数只要 $\ge 0$ 即可，于是插板法就行了，组合数由于 $n$ 很小可以直接算。

简单来说这题就是由于 $k$ 很小，可以通过容斥把等于零变成大于等于零，于是没有上限可以用插板法解决。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k1,k2;

typedef long long ll;

#define MOD 1000000007

ll power(ll a,int b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

ll C(int n,int m)

{

	ll res = 1;

	for(int i = n - m + 1;i <= n;++i)res = res * i % MOD;

	for(int i = 1;i <= m;++i)res = res * power(i,MOD - 2) % MOD;

	return res;

}

#define MAXK 9

ll u[MAXK << 1];

ll sum;

ll ans;

void dfs(int pos,ll tmp,int type)

{

	if(pos == n + 1)

	{

		if(tmp < 0)return;

		ans = (ans + type * C(tmp + n,n) + MOD) % MOD;

		return;

	}

	tmp -= u[pos] + 1;dfs(pos + 1,tmp,-type);

	tmp += u[pos] + 1;dfs(pos + 1,tmp,type);

	return;

}

void work()

{

	scanf("%d",&k1);

	int l,r;

	sum = 0;

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

	{

		scanf("%d%d",&l,&r);

		u[i] = r - l;sum += r;

	}

	scanf("%d",&k2);

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

	{

		scanf("%d%d",&l,&r);

		u[k1 + i] = r - l;sum -= l;

	}

	n = k1 + k2;

	u[n + 1] = 1000000000;

	--sum;

	ll ans1 = 0,ans2 = 0,ans3 = 0;

	if(sum < 0)ans1 = 0;

	else

	{

		ans = 0;

		dfs(1,sum,1);

		ans1 = ans;

	}

	ans = 0;++sum;

	if(sum < 0)ans = 0;

	else dfs(1,sum,1);

	ans2 = (ans - ans1 + MOD) % MOD;

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

	{

		ans1 = ans1 * power(u[i] + 1,MOD - 2) % MOD;

		ans2 = ans2 * power(u[i] + 1,MOD - 2) % MOD;

	}

	ans3 = (1 - ans1 + MOD - ans2 + MOD) % MOD;

	cout << ans1 << " " << ans2 << " " << ans3 << endl;

	return;

}

int main()

{

	int testcases = 0;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}