+-- 26 lines: #includes ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+-- 17 lines: pre-written code --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const long long MOD = 1000000007;
vector<long long> generate(long long seed, int n, long long a, long long b, long long c, long long d) {
vector<long long> answer(1,seed);
for (int i=1; i<n; ++i) {
long long last = answer.back();
long long curr = (last * a + b) % c + d;
answer.push_back(curr);
}
return answer;
}
struct edge { int to; long long length; };
vector<long long> dijkstra(const vector< vector<edge> > &graph, int source) {
vector<long long> min_distance( graph.size(), 1LL << 50 );
min_distance[ source ] = 0;
set< pair<long long,int> > active_vertices;
active_vertices.insert( {0,source} );
while (!active_vertices.empty()) {
int where = active_vertices.begin()->second;
active_vertices.erase( active_vertices.begin() );
for (auto ed : graph[where])
if (min_distance[ed.to] > min_distance[where] + ed.length) {
active_vertices.erase( { min_distance[ed.to], ed.to } );
min_distance[ed.to] = min_distance[where] + ed.length;
active_vertices.insert( { min_distance[ed.to], ed.to } );
}
}
return min_distance;
}
int N;
vector<long long> O, R, centerdist, clockwise, counterclockwise, pcenter, pcw, pccw;
vector< vector<edge> > G;
long long rataj(long long start) {
long long answer = 0;
int lo = 0, hi = N;
while (hi - lo > 1) {
int med = (lo+hi) / 2;
long long cwdist = clockwise[start+med] - clockwise[start];
long long ccwdist = counterclockwise[(N-start)+(N-med)] - counterclockwise[N-start];
if (cwdist < ccwdist) lo = med; else hi = med;
}
if (lo > 0) {
if (centerdist[start] + centerdist[start+lo] >= clockwise[start+lo] - clockwise[start]) {
long long znuly = pcw[start+lo+1] - pcw[start+1];
long long pridaj = znuly - lo * clockwise[start];
answer += pridaj;
answer %= MOD;
} else {
int rlo = 0, rhi = lo;
while (rhi - rlo > 1) {
int rmed = (rlo + rhi) / 2;
if (centerdist[start] + centerdist[start+rmed] >= clockwise[start+rmed] - clockwise[start]) rlo = rmed; else rhi = rmed;
}
long long znuly = pcw[start+rlo+1] - pcw[start+1];
long long pridaj = znuly - rlo * clockwise[start];
answer += pridaj;
pridaj = (lo-rlo) * centerdist[start] + pcenter[start+lo+1] - pcenter[start+rlo+1];
answer += pridaj;
answer %= MOD;
}
}
if (lo < N-1) {
lo = N-1-lo;
if (centerdist[start+N] + centerdist[start+N-lo] >= clockwise[start+N] - clockwise[start+N-lo]) {
long long znuly = pccw[N-start+lo+1] - pccw[N-start+1];
long long pridaj = znuly - lo * counterclockwise[N-start];
answer += pridaj;
answer %= MOD;
} else {
int rlo = 0, rhi = lo;
while (rhi - rlo > 1) {
int rmed = (rlo + rhi) / 2;
if (centerdist[start+N] + centerdist[start+N-rmed] >= clockwise[start+N] - clockwise[start+N-rmed]) rlo = rmed; else rhi = rmed;
}
long long znuly = pccw[N-start+rlo+1] - pccw[N-start+1];
long long pridaj = znuly - rlo * counterclockwise[N-start];
answer += pridaj;
answer += (lo-rlo) * centerdist[start] + pcenter[start+N-rlo] - pcenter[start+N-lo];
answer %= MOD;
}
}
answer %= MOD;
answer += MOD;
answer %= MOD;
return answer;
}
int main(int argc, char **argv) {
int mylo, myhi;
stringstream(argv[1]) >> mylo;
stringstream(argv[2]) >> myhi;
int T;
cin >> T;
for (int t=1; t<=T; ++t) {
cin >> N;
long long oseed, oa, ob, oc, od;
cin >> oseed >> oa >> ob >> oc >> od;
long long rseed, ra, rb, rc, rd;
cin >> rseed >> ra >> rb >> rc >> rd;
if (!(mylo <= t && t <= myhi)) continue;
O = generate(oseed,N,oa,ob,oc,od);
R = generate(rseed,N,ra,rb,rc,rd);
G.clear();
G.resize(N+1);
for (int n=0; n<N; ++n) {
G[n].push_back( { (n+1)%N, O[n] } );
G[(n+1)%N].push_back( { n, O[n] } );
}
for (int n=0; n<N; ++n) {
G[N].push_back( { n, R[n] } );
G[n].push_back( { N, R[n] } );
}
centerdist = dijkstra(G,N);
centerdist.pop_back();
centerdist.insert( centerdist.end(), centerdist.begin(), centerdist.end() );
centerdist.insert( centerdist.end(), centerdist.begin(), centerdist.end() );
pcenter.clear();
pcenter.resize(1,0);
for (auto x : centerdist) pcenter.push_back( (pcenter.back() + x) % MOD );
clockwise.clear();
clockwise.resize(1,0);
for (int n=0; n<=2*N+3; ++n) clockwise.push_back( clockwise.back() + O[n%N] );
counterclockwise.clear();
counterclockwise.resize(1,0);
for (int n=0; n<=2*N+3; ++n) counterclockwise.push_back( counterclockwise.back() + O[(10*N-1-n)%N] );
pcw.clear();
pcw.resize(1,0);
for (auto x : clockwise) pcw.push_back( (pcw.back() + x) % MOD );
pccw.clear();
pccw.resize(1,0);
for (auto x : counterclockwise) pccw.push_back( (pccw.back() + x) % MOD );
long long answer = 0;
for (int n=0; n<N; ++n) {
answer += rataj(n);
answer %= MOD;
}
answer *= 500000004;
answer %= MOD;
answer += accumulate( centerdist.begin(), centerdist.begin()+N, 0LL );
answer %= MOD;
cout << "Case #" << t << ": " << answer << endl;
}
}