Problem: sluggishsecurity (2017 round3)

**N** pairs of friends are standing in two lines of **N** people each, waiting to go through an airport security checkpoint. The _i_th passenger in the first line (counting from the front) belongs to pair **Ai**, while the _i_th passenger in the second line belongs to pair **Bi**. In the 2**N** integers **Ai..N**, and **Bi..N**, each value from 1 and **N** appears exactly twice. A pair of friends might be standing in the same line or in different lines. 

Every minute, the first person in one of the two lines will be admitted
through security. If one of the lines is already empty, then the person at the
front of the other line will necessarily be admitted. This process will go on
for 2**N** minutes, until both lines have been exhausted. Some people are much
slower than others at the tedious process of removing their shoes and belts,
placing their laptops in separate bins, and so on. As such, it's unclear which
line will be chosen to advance in each minute.

When a passenger passes through security, they will wait just past the
checkpoint for their friend (the other person in their pair) to also make it
through. If their friend has already made it through first, then the two of
them will immediately proceed to their gate. As such, if a pair of friends
pass through security after **a** and **b** minutes respectively, they will be
able to head to their gate after max(**a**, **b**) minutes. However, everyone
hates standing around after security for too long! If anyone is forced to wait
for their friend for more than 2 minutes (that is, max(**a**, **b**) >
min(**a**, **b**) + 2), then they'll throw a fit and the entire airport will
be closed down.

Assuming that everyone is satisfied and manages to get through security
without closing down the airport, sorting the pairs of friends by the times at
which they proceed to their gates yields a permutation of **N** pair numbers.
How many such pair orders are possible (modulo 1,000,000,007)?

In order to reduce the size of your input file, you're given **A1**, and
**A2..N** can be calculated as follows:

**Ai** = **Ai-1** \+ **DA,i-1**

In order to compute the sequence **DA,1..(N-1)**, you're given **KA** other
sequences, the _i_th of which consists of **LA,i** elements **SA,i,1..LA,i**,
and has an associated repetition number **RA,i**. The sequence **DA,1..(N-1)**
can then be constructed by concatenating together **KA** sequences, the _i_th
of which consists of the sequence **SA,i,1..LA,i** repeated **RA,i** times.
It's guaranteed that the concatenation of these repeated sequences has exactly
**N** \- 1 elements (in other words, the sum of the products **LA,i** *
**RA,i** for _i_ = 1..**KA** is equal to **N** \- 1).

In the same way, you're given **B1**, and **B2..N** can be calculated using
the sequence **DB,1..(N-1)**, which in turn can be calculated by concatenating
together **KB** sequences, the _i_th of which consists of **RB,i** copies of
the sequence **SB,i,1..LB,i**.

### Input

Input begins with an integer **T**, the number of different airports. For each
airport, there is first a line containing the integer **N**.

There is then a line with two space-separated integers **A1** and **KA**. Then
there are **KA** lines, the _i_th of which contains two space-separated
integers **RA,i** and **LA,i**, followed by **LA,i** more space-separated
integers, the _j_th of which is **SA,i,j**.

Similarly, there is then a line with two space-separated integers **B1** and
**KB**. Then there are **KB** lines, the _i_th of which contains two space-
separated integers **RB,i** and **LB,i**, followed by **LB,i** more space-
separated integers, the _j_th of which is **SB,i,j**.

### Output

For the _i_th airport, print a line containing "Case #**i**: " followed by the
number of possible pair orders, modulo 1,000,000,007. If it's not possible for
everybody to get through security without somebody throwing a tantrum, output
0.

### Constraints

1 ≤ **T** ≤ 400  
2 ≤ **N** ≤ 2,000,000  
1 ≤ **Ai**, **Bi**, **KA**, **KB**, **RA,i**, **RB,i**, **LA,i**, **LB,i** ≤
**N**  
-**N** ≤ **DA,i**, **DB,i**, **SA,i,j**, **SB,i,j** ≤ **N**   

### Explanation of Sample

In the first case, A = [1, 3, 2] and B = [3, 1, 2]. The two possible pair
orders are [1, 3, 2] and [3, 1, 2]. One way to achieve the former is to admit
passengers from lines 1, 2, 2, 1, 1, and 2 (who belong to pairs 1, 3, 1, 3, 2,
and 2).

In the second case, A = B = [1, 2, 3, 4, 5]. There is only one possible pair
order: [1, 2, 3, 4, 5].

In the third case, A = [2, 12, 5, 12, 5, 7, 1, 7, 4, 4, 15, 10, 15, 10, 14]
and B = [6, 6, 8, 8, 11, 2, 11, 13, 9, 13, 9, 3, 3, 1, 14].

In the fourth case, A = [1, 2, 3, 4, 5] and B = [5, 4, 3, 2, 1]. There's no
way for all of these people to get through security without causing a ruckus.

In the fifth case, A = [1, 1, 2, 2, ..., 4999, 4999, 5000, 5000] and B =
[5001, 5001, 5002, 5002, ..., 9999, 9999, 10000, 10000].



Sample input:
5
3
1 1
1 2 2 -1
3 2
1 1 -2
1 1 1
5
1 1
4 1 1
1 1
4 1 1
15
2 1
1 14 10 -7 7 -7 2 -6 6 -3 0 11 -5 5 -5 4
6 1
1 14 0 2 0 3 -9 9 2 -4 4 -4 -6 0 -2 13
5
1 1
4 1 1
5 1
4 1 -1
10000
1 2
4999 2 0 1
1 1 0
5001 2
4999 2 0 1
1 1 0


Sample output:
Case #1: 2
Case #2: 1
Case #3: 12
Case #4: 0
Case #5: 2413012



Code: // Hacker Cup 2017
// Round 3
// Sluggish Security
// Jacob Plachta

#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); }

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

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 2000005
#define MOD 1000000007

int A[LIM],B[LIM],S[LIM];
LL fct[LIM],ifct[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 Ch(int n,int k)
{
	return(fct[n]*ifct[k]%MOD*ifct[n-k]%MOD);
}

int main()
{
	// vars
	int T,t;
	int N,Ka,Kb;
	int i,j,a,b;
	int ans;
	// precompute factorials and their modular inverses
		Fox(i,LIM)
		{
			fct[i]=i ? fct[i-1]*i%MOD : 1;
			ifct[i]=gcd(fct[i],MOD).x;
				if (ifct[i]<0)
					ifct[i]+=MOD;
		}
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N);
			Read(A[0]),Read(Ka),N=1;
				while (Ka--)
				{
					Read(a),Read(b);
						Fox(i,b)
							Read(S[i]);
						while (a--)
							Fox(i,b) {
								A[N]=A[N-1]+S[i];
								N++;
							}
				}
			Read(B[0]),Read(Kb),N=1;
				while (Kb--)
				{
					Read(a),Read(b);
						Fox(i,b)
							Read(S[i]);
						while (a--)
							Fox(i,b) {
								B[N]=B[N-1]+S[i];
								N++;
							}
				}
			// pad arrays
			a=-1;
				Fox(j,4)
				{
					A[N+j]=a--;
					B[N+j]=a--;
				}
			// iterate through
			ans=1;
			i=j=a=b=0;
				while ((i<N) || (j<N))
					if (
						(A[i]==B[j]) ||
						(A[i]==B[j+1]) && (A[i+1]==B[j]) ||
						(A[i]==A[i+2]) && (A[i+1]==B[j]) ||
						(B[j]==B[j+2]) && (B[j+1]==A[i])
					) {
						// cross pattern, must end current streaks
						ans=(LL)ans*Ch(a+b,a)%MOD;
						a=b=0;
							if (A[i]==B[j])
								i++,j++;
							else
							{
								ans=(ans<<1)%MOD;
									if (A[i]==A[i+2])
										i+=3,j++;
									else
									if (B[j]==B[j+2])
										j+=3,i++;
									else
										i+=2,j+=2;
							}
					}
					else
					// continue one of the current streaks?
					if (A[i]==A[i+1])
						i+=2,a++;
					else
					if (B[j]==B[j+1])
						j+=2,b++;
					else
					if ((A[i]==A[i+2]) && (A[i+1]==A[i+3]))
						i+=4,a++;
					else
					if ((B[j]==B[j+2]) && (B[j+1]==B[j+3]))
						j+=4,b++;
					else
					{
						// impossible pattern
						ans=0;
						break;
					}
			ans=(LL)ans*Ch(a+b,a)%MOD;
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}