Problem: fightingallthezombies (2017 round2)

At last, your power knows no bounds! Within the world of the ever-popular
role-playing game _Dungeons & Dragons_, or _D&D_, you've managed to become one
of the most powerful wizards to have ever wizarded.

And yet, you're still not content — you feel compelled to continue grinding
away, repeatedly destroying monsters to ever so slowly increase your power
further. There's a particular cave which contains **N** zombies, and these
zombies respawn every time you reenter the cave. As such, you can efficiently
gain experience by entering, destroying all of them, and leaving, repeating
this process infinitely (or until your supply of Hot Pockets runs out). The
_n_th zombie has a power level of _n_.

Conveniently, you're also carrying **N** wands with you, the _n_th of which
has a power level of _n_. Each time you enter the cave, you'll use each of
your wands exactly once to cast a spell and destroy a single zombie, such that
all **N** zombies are defeated. Initially, you know **N** different spells,
the _n_th of which allows your wand with power level _n_ to target the zombie
with power level _n_.

You're going to visit the cave **M** times today. Before each visit, you're
going to learn some new spells (which you'll continue to be able to use for
all of your remaining visits). In particular, before your _i_th visit, you'll
acquire **Si** different new spells, each of which allows your wand with power
level **Wi** to target the zombie with power level of **Zi**. Wands are unable
to affect zombies which are much more powerful than them, and it would be a
waste to use a wand on a zombie much weaker than it. As such, |**Wi** \-
**Zi**| ≤ 1 holds for all spells. Note that all spells are considered
distinct, even if several of them allow a particular wand to target a
particular zombie.

On each of your **M** visits to the cave, you're interested in the number of
different ways in which you can defeat all **N** zombies, using only the
spells that you've learned up to that point. Two ways are considered different
if at least one spell is used in one of them but not the other. These
quantities can get rather large, and you don't want to deal with **M** big
numbers, so you only care about computing their sum modulo 1,000,000,007.

You're given **W1**, and **W2..M** may then be calculated as follows, using
given constants **Aw** and **Bw**:

**Wi** = ((**Aw** * **Wi-1** \+ **Bw**) % **N**) + 1 

A temporary sequence of values **D1..M** will be used to help calculate
**Z1..M**. You're given **D1**, and **D2..M** may then be calculated as
follows, using given constants **Ad** and **Bd**:

**Di** = (**Ad** * **Di-1** \+ **Bd**) % 3 

From these values, **Z1..M** may then be calculated as follows:

**Zi** = max{ 1, min { **N**, **Wi** \+ **Di** \- 1} } 

Finally, you're given **S1**, and **S2..M** may then be calculated as follows,
using given constants **As** and **Bs**:

**Si** = ((**As** * **Si-1** \+ **Bs**) % 1,000,000,000) + 1 

### Input

Input begins with an integer **T**, the number of different caves you'll
visit. For each cave, there are four lines. The first line contains the two
space-separated integers **N** and **M**. The second line contains the three
space-separated integers **W1**, **Aw**, and **Bw**. The third line contains
the three space-separated integers **D1**, **Ad**, and **Bd**. The fourth line
contains the three space-separated integers **S1**, **As**, and **Bs**.

### Output

For the _i_th cave, print a line containing "Case #**i**: " followed by one
integer. This number is the sum (taken modulo 1,000,000,007) of **M** values,
the _j_th of which is the number of different ways in which you can defeat the
zombies on your _j_th visit to the cave.

### Constraints

1 ≤ **T** ≤ 20  
1 ≤ **N**, **M** ≤ 800,000  
1 ≤ **W1** ≤ **N**  
0 ≤ **Aw**, **Bw** ≤ **N** \- 1  
0 ≤ **D1**, **Ad**, **Bd** ≤ 2  
1 ≤ **S1**, **As**, **Bs** ≤ 1,000,000,000  

### Explanation of Sample

In the first case, your first learn a new spell that can defeat the first
zombie with your first wand. This gives you 2 ways to defeat the first zombie
with your first wand, and 1 way to defeat the second zombie with your second
wand, for a total of 2 ways to defeat both.

You then learn three new ways to defeat the second zombie with your second
wand. 2 ways to defeat the first zombie and 4 ways to defeat the second zombie
is 8 ways to defeat both.

You then learn five new ways to defeat the second zombie with your first wand.
You can't actually use your first wand to defeat the second zombie though, as
that will leave you with no ways to defeat the first zombie. So you still have
8 ways to defeat both.

Finally, you learn seven new ways to defeat the first zombie with the second
wand. If you use the first wand on the first zombie, and the second wand on
the second zombie, you still have 8 combinations of possible spells. If you
use the first wand on the second zombie and second wand on the first zombie,
you have 7 * 5 = 35 combinations of possible spells. In total, that's 43 ways
to defeat the zombies.

Therefore the total answer is 2 + 8 + 8 + 43 = 61.



Sample input:
5
2 4
1 1 0
0 1 1
1 1 1
4 8
1 1 0
0 1 1
1 1 1
5 20
1 1 1
1 1 2
3 5 7
10 30
5 5 5
0 1 1
1 1 1
800 4000
13 17 23
2 1 1
29 31 37


Sample output:
Case #1: 61
Case #2: 34043
Case #3: 192619805
Case #4: 6300
Case #5: 118131145



Code: // Hacker Cup 2017
// Round 2
// Fighting all the Zombies
// 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 2100000
#define MOD 1000000007
 
int sz,tree[LIM][2][2];
int V1[LIM],V2[LIM],V3[LIM];
 
void Add(int &a,int b)
{
    a+=b;
        if (a>=MOD)
            a-=MOD;
}
 
void Calc(int i)
{
        if (i>=sz)
        {
            tree[i][0][0]=V1[i-sz];
            tree[i][0][1]=(LL)V2[i-sz]*V3[i-sz]%MOD;
            tree[i][1][0]=1;
            tree[i][1][1]=0;
            return;
        }
    int j=i<<1,k=j+1,a,b,c;
    Fill(tree[i],0);
        Fox(a,2)
            Fox(b,2)
                Fox(c,2)
                    Add(tree[i][a][b],(LL)tree[j][a][c]*tree[k][c][b]%MOD);
}
 
int main()
{
    int T,t;
    int N,M,Z;
    int W,Aw,Bw;
    int D,Ad,Bd;
    int S,As,Bs;
    int i,tot;
    Read(T);
        Fox1(t,T)
        {
            Read(N),Read(M);
            Read(W),Read(Aw),Read(Bw);
            Read(D),Read(Ad),Read(Bd);
            Read(S),Read(As),Read(Bs);
                for(sz=1;sz<N;sz<<=1);
                Fox(i,sz)
                    V1[i]=1;
            Fill(V2,0);
            Fill(V3,0);
                FoxR1(i,(sz<<1)-1)
                    Calc(i);
            tot=0;
                while (M--)
                {
                    Z=max(1,min(N,W+D-1));
                        if (W==Z)
                            Add(V1[W-1],S);
                        else
                        if (W<Z)
                            Add(V2[W-1],S);
                        else
                            Add(V3[Z-1],S);
                    i=min(W-1,Z-1)+sz;
                        while (i)
                            Calc(i),i>>=1;
                    Add(tot,tree[1][0][0]);
                    W=((LL)Aw*W+Bw)%N+1;
                    D=((LL)Ad*D+Bd)%3;
                    S=((LL)As*S+Bs)%INF+1;
                }
            printf("Case #%d: %d\n",t,tot);
        }
    return(0);
}