Problem: evening (2018 round1)

A quiet evening has set over a residential area. As families sit down for
supper in the safety of their homes, a calm atmosphere permeates the outside
air. The neighborhood feels truly at peace, separated from the frenzy of the
rest of the world. Also, a bunch of zombies have just risen out of the ground
and want to eat everybody.

The neighborhood has **N** yards in a row, numbered from 1 to **N**. There are
also **N**-1 fences, one between each pair of adjacent yards. The fence
between yards _i_ and _i_+1 has an unknown integral height drawn uniformly at
random from the inclusive interval [**Ai**, **Bi**]. In other words, the _i_th
fence has **Bi** \- **Ai** \+ 1 possible heights, each of which is equally
likely.

**M** hungry zombies are also present, with the _i_th of them initially in yard **Yi**. Fortunately for the zombies, they might not be stopped by the surrounding fences so easily. The _i_th zombie has the ability to climb over any fence with a height of at most **Hi**. It may repeatedly move from its current yard to an adjacent one, as long as the fence between the yards is no taller than **Hi**. Multiple zombies may start in the same yard, and multiple zombies may occupy the same yard at any point. 

A yard is considered "safe" if it's impossible for any zombies to ever reach
it. Determine the probability that at least one of the **N** yards is safe.
Let this probability be represented as a quotient of integers _p_/_q_ in
lowest terms. Output the value of this quotient modulo 1,000,000,007 — in
other words, output the unique integer _x_ such that 0 ≤ _x_ < 1,000,000,007
and _p_ = _x_*_q_ (modulo 1,000,000,007).

### Input

Input begins with an integer **T**, the number of neighborhoods. For each
neighborhood, there is first a line containing the space-separated integers
**N** and **M**. Then, **N-1** lines follow. The _i_th of these lines contains
the space-separated integers **Ai** and **Bi**. Then, **M** lines follow. The
_i_th of these lines contains the space-separated integers **Yi** and **Hi**.

### Output

For the _i_th neighborhood, print a line containing "Case #_i_: " followed by
1 integer, the probability that at least one of the yards is safe, expressed
as a quotient of integers modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 75  
1 ≤ **N** ≤ 3,000  
1 ≤ **M** ≤ 3,000  
1 ≤ **Ai** ≤ **Bi** ≤ 1,000,000  
1 ≤ **Yi** ≤ **N**  
1 ≤ **Hi** ≤ 1,000,000  

### Explanation of Sample

In the first case, if the height of the single fence is 100, then the zombie
in yard 1 will be able to climb over it to reach yard 2, meaning that no yards
will be safe. Otherwise, if the fence's height is 101, then yard 2 will be
safe. Therefore, the probability that at least one of the yards is safe is 1/2
= 500000004 (modulo 1,000,000,007).

In the second case, in order for yard 2 to be safe from both surrounding
zombies, the first fence's height must be either 3 or 4, and the second
fence's height must be 4. The probability of this occurring is 2/4 * 1/4 = 1/8
= 125000001 (modulo 1,000,000,007).

In the third case, the probability of at least one yard being safe is 2/3 =
666666672 (modulo 1,000,000,007).



Sample input:
6
2 1
100 101
1 100
3 2
1 4
1 4
1 2
3 3
4 2
1 4
1 2
3 5
4 3
3 1
6 3
1 20
2 19
3 18
4 17
5 16
6 9
1 13
6 7
6 3
1 20
2 19
3 18
4 17
5 16
4 9
3 13
4 7
16 10
10 40
5 55
20 25
25 50
40 65
35 50
15 20
10 35
15 55
10 70
25 60
5 50
20 50
10 30
15 55
9 32
14 48
5 34
13 41
7 35
2 19
13 20
5 17
3 33
11 24


Sample output:
Case #1: 500000004
Case #2: 125000001
Case #3: 666666672
Case #4: 417224706
Case #5: 441220242
Case #6: 292643605



Code: // Evening of the Living Dead
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 3003
#define MOD 1000000007

int A[LIM],B[LIM];

PR GCD(int a,int b)
{
		if (!b)
			return(mp(1,0));
	PR p=GCD(b,a%b);
	return(mp(p.y,p.x-p.y*(a/b)));
}

int Add(int a,int b)
{
	return((a+b)%MOD);
}

int Sub(int a,int b)
{
	return((a-b+MOD)%MOD);
}

int Mult(int a,int b)
{
	return((LL)a*b%MOD);
}

int Div(int a,int b)
{
	int inv=GCD(b,MOD).x;
		if (inv<0)
			inv+=MOD;
	return(Mult(a,inv));
}

int Prob(int i,int a,int b)
{
	Max(a,A[i]);
	Min(b,B[i]);
		if (a>b)
			return(0);
	return(Div(b-a+1,B[i]-A[i]+1));
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N,M;
	int i,j,h,z,d,p,ans;
	int mH[LIM];
	int nh,H[LIM];
	static int dynSafe[LIM][LIM]; // [yard][max fence height protecting safe yard]
	static int dynZomb[LIM][LIM]; // [yard][max active zombie height]
	int aggr[LIM];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N),Read(M);
				Fox(i,N-1)
					Read(A[i]),Read(B[i]);
			Fill(mH,0);
				Fox(i,M)
				{
					Read(j),Read(h);
					Max(mH[j-1],h);
				}
			// coordinate compress zombie heights
			nh=0;
			H[nh++]=0;
			H[nh++]=INF;
				Fox(i,N)
					if (mH[i])
						H[nh++]=mH[i];
			sort(H,H+nh);
			nh=unique(H,H+nh)-H;
				Fox(i,N)
					mH[i]=lower_bound(H,H+nh,mH[i])-H;
			// DP
			Fill(dynSafe,0);
			Fill(dynZomb,0);
				if (mH[0])
					dynZomb[1][mH[0]]=1;
				else
					dynSafe[1][0]=1;
				Fox1(i,N-1)
				{
					Fill(aggr,0);
						Fox(h,nh)
						{
							z=mH[i];
								if (d=dynSafe[i][h])
								{
									// new zombie's lower anyway?
									if ((!z) || (z<h))
									{
										// new fence is no taller?
										p=Prob(i-1,0,H[h]);
										dynSafe[i+1][h]=Add(dynSafe[i+1][h],Mult(d,p));
										// new fence is taller?
										aggr[h+1]=Add(aggr[h+1],d); // aggregate
									}
									else
									{
										// new fence is no taller than the zombie?
										p=Prob(i-1,0,H[z]);
										dynZomb[i+1][z]=Add(dynZomb[i+1][z],Mult(d,p));
										// new fence is taller?
										aggr[z+1]=Add(aggr[z+1],d); // aggregate
									}
								}
								if (d=dynZomb[i][h])
								{
									// new zombie's at least as tall?
									if (z>=h)
										dynZomb[i+1][z]=Add(dynZomb[i+1][z],d);
									else
									{
										// prev zombie carrying over?
										p=Prob(i-1,0,H[h]);
										dynZomb[i+1][h]=Add(dynZomb[i+1][h],Mult(d,p));
										// not carrying over?
										p=Sub(1,p);
											if (z) // new zombie
												dynZomb[i+1][z]=Add(dynZomb[i+1][z],Mult(d,p));
											else // now safe
												dynSafe[i+1][0]=Add(dynSafe[i+1][0],Mult(d,p));
									}
								}
						}
					// handle aggregated transitions
					d=0;
						Fox1(j,nh-1)
						{
							d=Add(d,aggr[j]);
								if (d)
								{
									p=Prob(i-1,H[j-1]+1,H[j]);
									dynSafe[i+1][j]=Add(dynSafe[i+1][j],Mult(d,p));
								}
						}
				}
			// compute answer
			ans=0;
				Fox(h,nh)
					ans=Add(ans,dynSafe[N][h]);
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}