A2.cpp

#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// DONT USE MEMSET, USE VECTORS



ll mod = 1e9+7;
vector<ll>l;
vector<ll>h;
vector<ll>w;
void solve(){
	int n,k;
	cin>>n>>k;
	l.resize(n+1);
	w.resize(n+1);
	h.resize(n+1);

	for(int i=1;i<=k;i++){
		cin>>l[i];
	}
	ll al,bl,cl,dl;
	cin>>al>>bl>>cl>>dl;

	for(int i=1;i<=k;i++){
		cin>>w[i];
	}
	ll aw,bw,cw,dw;
	cin>>aw>>bw>>cw>>dw;

	for(int i=1;i<=k;i++){
		cin>>h[i];
	}

	ll ah,bh,ch,dh;
	cin>>ah>>bh>>ch>>dh;

	for(int i=k+1;i<=n;i++){
		////cerr<<"there "<<i<<endl;
		l[i] = ((al*l[i-2]+bl*l[i-1]+cl)%dl)+1;
		h[i] = ((ah*h[i-2]+bh*h[i-1]+ch)%dh)+1;
		w[i] = ((aw*w[i-2]+bw*w[i-1]+cw)%dw)+1;
	}

	set<pair<ll,pair<ll,ll>>> ls;

	ls.insert({l[1],{l[1]+w[1],h[1]}});
	ll curp = (w[1] + h[1])*2;
	curp %= mod;
	ll ans  = curp;

	//cerr<<curp<<endl;

	for(int i=2;i<=n;i++){
		auto lpt = ls.lower_bound({l[i],{0,0}});
		auto rpt = ls.upper_bound({l[i]+w[i],{0,0}});
		if(lpt != ls.begin()){
			auto tmp = lpt;
			tmp--;
			if(tmp->Y.X >= l[i]){
				lpt--;
			}
		}
		ll minl,maxr;
		minl = l[i];
		maxr = l[i]+w[i];
		ll mxh = h[i];
		// Erase without messing up the iteration.
		for(auto it = lpt; it!=ls.end() && it!=rpt;){
			// do stuff
			//cerr<<l[i]<<" , "<<l[i]+w[i]<<" intersects with "<<it->X<<" , "<<it->Y.X<<" which has height "<<it->Y.Y<<endl;
			minl = min(minl,it->X);
			maxr = max(maxr,it->Y.X);
			mxh += (it->Y.Y - h[i]);
			//cerr<<"Adding "<<(it->Y.Y - h[i])<<" to height "<<endl;
			curp -= (it->Y.X - it->X + it->Y.Y)*2;
			curp = (curp + mod)%mod;
			//cerr<<"Subtracting "<<(it->Y.X - it->X + it->Y.Y)*2<<" from curp "<<endl;
			ls.erase(it++);
		}
		//cerr<<"New segment is "<<minl<<" "<<maxr<<" with height "<<mxh<<endl;
		//cerr<<(maxr-minl + mxh)*2<<endl;;
		curp += (maxr-minl + mxh)*2;
		curp %= mod;
		ls.insert({minl,{maxr,mxh}});

		//cerr<<curp<<endl;
		ans *= curp;
		ans %= mod;

	}
	cout<<ans<<endl;


}

int main(){
	fastread;
	int t = 1;
	cin>>t;
	for(int i=1;i<=t;i++){
		cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}