Arc of Dream

solution

[ A x A y 0 0 0 0 1 0 0 0 0 B y B x 0 0 A x B y A y B y A y B x A x B x 0 0 0 0 1 1 ] n \left[ \begin{matrix} Ax & Ay & 0 & 0 & 0 \\0 & 1 & 0 & 0 & 0 \\0 & By & Bx & 0 & 0 \\AxBy & AyBy & AyBx & AxBx & 0 \\0 & 0 & 0 & 1 & 1 \end{matrix} \right]^{n} ⎣⎢⎢⎢⎢⎡​Ax00AxBy0​Ay1ByAyBy0​00BxAyBx0​000AxBx1​00001​⎦⎥⎥⎥⎥⎤​n* [ A 0 1 B 0 A 0 B 0 0 ] \left[ \begin{matrix} A_0 \\1 \\B_0 \\A_0B_0 \\0 \end{matrix} \right] ⎣⎢⎢⎢⎢⎡​A0​1B0​A0​B0​0​⎦⎥⎥⎥⎥⎤​ = [ A n 1 B n A n B n ∑ i = 0 n − 1 A 0 B 0 ] \left[ \begin{matrix} A_n \\1 \\B_n \\A_nB_n \\\sum\limits_{i=0}^{n-1}A_0B_0 \end{matrix} \right] ⎣⎢⎢⎢⎢⎢⎢⎡​An​1Bn​An​Bn​i=0∑n−1​A0​B0​​⎦⎥⎥⎥⎥⎥⎥⎤​

code

/*SiberianSquirrel*/
/*CuteKiloFish*/
#include<bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

long long A0, Ax, Ay, B0, Bx, By, n;

typedef struct Matrix {
    long long mx[5][5];
    void Init(long long a0, long long ax, long long ay, long long b0, long long bx, long long by) {
        mx[0][0] = ax, mx[0][1] = ay, mx[0][2] = 0, mx[0][3] = 0, mx[0][4] = 0;
        mx[1][0] = 0, mx[1][1] = 1, mx[1][2] = 0, mx[1][3] = 0, mx[1][4] = 0;
        mx[2][0] = 0, mx[2][1] = by, mx[2][2] = bx, mx[2][3] = 0, mx[2][4] = 0;
        mx[3][0] = ax*by%MOD, mx[3][1] = ay*by%MOD, mx[3][2] = ay*bx%MOD, mx[3][3] = ax*bx%MOD, mx[3][4] = 0;
        mx[4][0] = 0, mx[4][1] = 0, mx[4][2] = 0, mx[4][3] = 1, mx[4][4] = 1;
    }
    void Out() {
        for(int i = 0; i < 5; ++i) {
            for(int j = 0; j < 5; ++j)
                cout << mx[i][j] << ' ';
            cout << endl;
        }
    }
    void Tranfer_E() {
        memset(mx, 0, sizeof mx);
        for(int i = 0; i < 5; ++ i) mx[i][i] = 1;
    }
    struct Matrix operator * (const struct Matrix a)const {
        struct Matrix x;
        memset(x.mx,0,sizeof(x.mx));
        for(int i = 0; i < 5; ++i)
            for(int j = 0; j < 5; ++j)
                for(int k = 0; k < 5; ++k)
                    x.mx[i][j] = (x.mx[i][j] + mx[i][k] * a.mx[k][j] % MOD + MOD) % MOD;
        return x;
    };
}Matrix;

Matrix mat_pow(Matrix mx, long long p) {
    Matrix res;
    res.Tranfer_E();
    for(; p; p >>= 1, mx = mx * mx)
        if(p & 1) res = res * mx;
    return res;
}

void solve() {
    Matrix x;
    x.Init(A0, Ax, Ay, B0, Bx, By);
    x = mat_pow(x, n);
//    x.Out();
    long long ans1 = x.mx[4][0] * A0 % MOD;
    long long ans2 = x.mx[4][1] * 1 % MOD;
    long long ans3 = x.mx[4][2] * B0 % MOD;
    long long ans4 = x.mx[4][3] * A0 % MOD * B0 % MOD;
    long long ans5 = x.mx[4][4] * 0 % MOD;
    cout << ((((ans1 + ans2) % MOD + ans3) % MOD + ans4) % MOD + ans5) % MOD << endl;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
#ifdef ACM_LOCAL
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif
    while(cin >> n) {
        cin >> A0 >> Ax >> Ay;
        cin >> B0 >> Bx >> By;
        A0 %= MOD, Ax %= MOD, Ay %= MOD;
        B0 %= MOD, Bx %= MOD, By %= MOD;
        solve();
    }
    return 0;
}