Problem: replay_value (2018 round2)

Allison has just developed the latest addictive mobile game: **Super Path
Drawer: Extreme Edition**!

This game takes place on an infinite 2D plane (thanks to advancements in
graphical technology, the entire plane can fit onto a mobile phone screen).
Two distinct points on the plane are chosen: a starting point (at coordinates
(0, **S**)), and an ending point (at coordinates (1,000,000,000, **E**)). The
player's goal is to draw a path from the starting point to the ending point.
The path may be any continuous curve on the plane (not necessarily a straight
line segment), and may cross itself. If the player successfully draws such a
path, they're rewarded with a "point", thus convincing them that their time is
being put to good use. If they fail to draw such a path, they're instead
forced to watch an ad, thus motivating them to do better on their next
attempt.

By itself, this game is certainly addicting, but it doesn't seem to cause
players to watch enough ads! So, as a last-minute addition, Allison has
inserted some lasers. There are **N** laser emitters, the _i_th of which is at
(**Xi**, **Yi**). Each emitter will emit a laser beam either directly up,
down, left, or right. The laser beam is a ray starting from the emitter's
position (inclusive) and continuing infinitely in the selected direction.
Naturally, the player's path may not touch any part of any laser beam. All
**N**+2 x-coordinates (of the starting point, ending point, and laser
emitters) are distinct, and all **N**+2 y-coordinates are also distinct,
meaning that it's impossible for a laser beam to ever directly hit the
starting point, ending point, or another emitter.

Allison hasn't programmed in the capability for moving laser emitters around,
but she can at least cause them to emit their laser beams in different
combinations of directions each time a player replays the game. She's
concerned that players will get bored as soon as they encounter a laser
configuration which they've already seen, so she'll make sure that each player
is presented with each of the 4**N** possible different laser configurations
exactly once.

Some laser configurations result in the ending point still being reachable
from the starting point by some continuous path which doesn't touch any laser
beams, in which case players will surely manage to find such a path. But for
other laser configurations, no valid path exists at all, resulting in a forced
ad showcase. Allison would like to count the total number of ads which a
player will end up watching upon playing the game once for each of the 4**N**
possible different laser configurations. As this value can be large, you only
need to compute it modulo 1,000,000,007.

### Input

Input begins with an integer **T**, the number of sets of lasers. For each set
of lasers, there is first a line containing the space-separated integers
**N**, **S**, and **E**. Then, **N** lines follow. The _i_th of these contains
the space-separated integers **Xi** and **Yi**.

### Output

For the _i_th set of lasers, output a line containing "Case #_i_: " followed
by the number of ads shown to each player, modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 30  
1 ≤ **N** ≤ 50  
0 ≤ **S**, **E**, **Xi**, **Yi** ≤ 1,000,000,000  

### Explanation of Sample

In the first case, 11 of the 64 possible laser configurations result in the
ending point being unreachable from the starting point. One such configuration
is when the first emitter points down, the second points up, and the third
points right. Another is when the first emitter points down, the second points
left, and the third points down.



Sample input:
4
3 100 1000
3333 3333
4321 123
1234 567
4 0 50
30 30
10 10
40 20
20 40
7 61 34
241 69
924 30
580 70
649 68
453 15
599 82
242 81
20 167851000 757147
336971124 301413356
160567225 659598368
4890851 391749387
26239572 35766290
597006 473038164
326051436 3615544
118341522 392289610
37215528 170427798
168544290 675016433
950090226 683447133
116752251 82426872
706221268 194041604
257655783 69909134
21417562 84970743
40873980 37379060
80835680 8670528
653352030 436291072
374079500 106923810
86546364 466701606
480572136 247776867


Sample output:
Case #1: 11
Case #2: 80
Case #3: 6799
Case #4: 981633474



Code: // Replay Value
// 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 52
#define MOD 1000000007

int dyn[2][LIM][LIM][LIM][LIM];
// dyn[i][a][b][c][d] = number of ways such that:
//   i = laser index
//   a = lowest Up
//   b = highest Down
//   c = lowest Right in regions 1/2
//   d = highest Right in region 3

int N;
vector<int> cy;

void ReadY(int &y)
{
	Read(y),cy.pb(y);
}

void CompY(int &y)
{
	y=lower_bound(All(cy),y)-cy.begin();
}

void Flip(int &v)
{
	v=N+1-v;
}

void Add(int &a,int b)
{
	a+=b;
		if (a>=MOD)
			a-=MOD;
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int YA,YB;
	int i,a,b,c,d,y,r,v,m,ans;
	int A,B;
	PR P[LIM];
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
			cy.clear();
			// input
			Read(N),ReadY(YA),ReadY(YB);
				Fox(i,N)
					Read(P[i].x),ReadY(P[i].y);
			// compress y-coordinates
			sort(All(cy));
			CompY(YA),CompY(YB);
				Fox(i,N)
					CompY(P[i].y);
			// mirror y-axis such that B is below A
				if (YA<YB)
				{
					Flip(YA),Flip(YB);
						Fox(i,N)
							Flip(P[i].y);
				}
			// sort lasers by increasing x
			sort(P,P+N);
			// DP
			Fill(dyn,0);
			A=0,B=1;
			dyn[B][N+1][0][N+1][0]=1;
				Fox(i,N)
				{
					// slide DP window
					swap(A,B);
					Fill(dyn[B],0);
					// compute laser's region
					y=P[i].y;
					r=(y>YA ? 1 : (y>YB ? 2 : 3));
					// perform transitions
						Fox(a,N+2)
							Fox(b,N+2)
								Fox(c,N+2)
									Fox(d,N+2)
										if (v=dyn[A][a][b][c][d])
										{
											// up
												if (y>=d)
													Add(dyn[B][min(a,y)][b][c][d],v);
											// down
												if (y<=c)
													Add(dyn[B][a][max(b,y)][c][d],v);
											// left
												if ((r==1 && y>=b) || (r>1 && y<=a))
													Add(dyn[B][a][b][c][d],v);
											// right
												if (r<3)
													Add(dyn[B][a][b][min(c,y)][d],v);
												else
													Add(dyn[B][a][b][c][max(d,y)],v);
										}
				}
			// compute answer
			ans=1;
				Fox(i,N)
					ans=(LL)ans*4%MOD;
			v=0;
				Fox(a,N+2)
					Fox(b,N+2)
						Fox(c,N+2)
							Fox(d,N+2)
								Add(v,dyn[B][a][b][c][d]);
			ans=(ans-v+MOD)%MOD;
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}