Problem: snake_and_ladder (2016 finals)

Some time has passed since you took in the local population of snakes, feeding
them every day and allowing them to live peacefully amongst your ladders.
Unfortunately, your neighbours have not been thrilled about living next to
billions of serpents, so they've filed complaints to the mayor! As a result,
almost all of your snakes and ladders have been forcibly evicted, leaving you
with only one of each for company.

Your ladder has **N** horizontal rungs, numbered 1 to **N** from bottom to
top. Like all ladders, it also has 2 vertical rails, with rail 1 on the left
and rail 2 on the right. To improve its appearance, you've allowed some plants
to grow all over it. Notably, there are **K** flowers at distinct locations on
the ladder, with the ith flower at the intersection of rung **R_i** and rail
**C_i**.

Your snake loves to sleep on the ladder. It always places its head at the
intersection of some rung and some rail, and from there, each subsequent
segment of its body extends up, down, left, or right to follow a rung or rail
to another intersection. The snake likes to be spread out, but hates touching
flowers, so it insists that the path that its body takes must not touch any
intersection more than once, and must not touch any intersection that has a
flower. Conveniently, the snake is exactly long enough to theoretically pass
through all intersections that don't have flowers — that is, if consecutive
rungs and rails are 1 unit apart from one another, then the snake has a length
of 2 * **N** \- **K** \- 1 units. Note that your snake may have 0 length (in
which case it'll only occupy a single intersection).

The diagram below (which corresponds to the fourth sample case) illustrates a
valid way in which the snake can arrange itself on a ladder with 4 rungs and 1
flower:

![]({{PHOTO_ID:191658972183607}})

Can you help your snake count the number of different ways in which it can
position itself on the ladder, such that it covers all of the intersections
which don't contain flowers? An arrangement of the snake is defined by an
ordered sequence of intersections that it passes through, starting from its
head. You only need to compute the answer modulo 109 \+ 7.

### Input

Input begins with an integer **T**, the number of ladders. For each ladder,
there is first a line containing the space-separated integers **N** and **K**.
Then **K** lines follow, the **i**th of which contains the space-separated
integers **Ri** and **Ci** .

### Output

For the **i**th ladder, print a line containing "Case #**i**: " followed by
the number of ways in which the snake can be arranged, modulo 109 \+ 7.

### Constraints

1 ≤ **T** ≤ 555  
1 ≤ **N** ≤ 1012  
0 ≤ **K** ≤ min(1000, 2 * **N** \- 1)  
1 ≤ **Ri** ≤ **N**  
1 ≤ **Ci** ≤ 2  

### Explanation of Sample

For the first ladder, the snake can place its head in any of the 4
intersections, and from each one it can arrange itself in 2 ways for 8 ways
total. For the second ladder, the flowers prevent the snake from crossing from
the top 2 intersections to the bottom 2 (or vice versa). For the third ladder,
there are 2 possible intersections at which the snake can place its head which
yield 1 valid arrangement each.



Sample input:
5
2 0
3 2
2 1
2 2
3 3
1 1
2 1
1 2
4 1
4 2
12345678 8
233487 1
12014429 2
25928 1
358726 2
9588722 1
13990 2
11573895 1
233488 1


Sample output:
Case #1: 8
Case #2: 0
Case #3: 2
Case #4: 6
Case #5: 267684459



Code: // SNAKE AND LADDER
// Official 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-9;
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);
}

bool ReadLL(LL &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 MOD 1000000007

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	int T,t;
	LL N;
	int K;
	int i,ans;
	LL a,b,x,y;
	static pair<LL,int> P[1000];
	Read(T);
		Fox1(t,T)
		{
			ReadLL(N),Read(K);
				Fox(i,K)
					ReadLL(P[i].x),Read(P[i].y);
				if (K==2*N-1)
				{
					ans=1;
					goto Done;
				}
			sort(P,P+K);
			a=1,b=N;
				Fox(i,K-1)
					if ((P[i].x==P[i+1].x) && (P[i].x==a))
						a++;
				FoxR(i,K-1)
					if ((P[i].x==P[i+1].x) && (P[i].x==b))
						b--;
			ans=0;
				Fox(i,K-1)
					if ((P[i].x==P[i+1].x) && (P[i].x>=a) && (P[i].x<=b))
						goto Done;
			x=-1;
				Fox(i,K)
					if ((P[i].x>=a) && (P[i].x<=b))
						if (x<0)
							x=y=P[i].x;
						else
						{
								if ((P[i].x-y)%2==(P[i].y+P[i-1].y)%2)
									goto Done;
							y=P[i].x;
						}
				if (x<0)
				{
					N=b-a+1;
						if (N==1)
							ans=2;
						else
						{
							N=(N-1)%MOD;
							ans=(4+2*N*(N+1))%MOD;
						}
				}
				else
				{
					a=max(1LL,x-a);
					b=max(1LL,b-y);
					ans=2*(a%MOD)*(b%MOD)%MOD;
				}
Done:;
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}