S - Arc of Dream 矩阵快速幂

An Arc of Dream is a curve defined by following function:
S - Arc of Dream 矩阵快速幂-LMLPHP

where
a  = A0
a  = a *AX+AY
b  = B0
b  = b *BX+BY
What is the value of AoD(N) modulo 1,000,000,007?

InputThere are multiple test cases. Process to the End of File.
Each test case contains 7 nonnegative integers as follows:
N
A0 AX AY
B0 BX BY
N is no more than 10 , and all the other integers are no more than 2×10 .OutputFor each test case, output AoD(N) modulo 1,000,000,007.Sample Input

Sample Output

| AX 0 AXBY AXBY 0 |

| 0 BX AYBX AYBX 0 |

{a[i-1] b[i-1] a[i-1]*b[i-1] AoD[i-1] 1}* | 0 0 AXBX AXBX 0 | = {a[i] b[i] a[i]*b[i] AoD[i] 1}

| 0 0 0 1 0 |

| AY BY AYBY AYBY 1 |

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<string>

using namespace std;

typedef unsigned long long LL;

#define MAXN 30

#define L 100006

#define MOD 1000000007

#define INF 1000000009

const double eps = 1e-;

/*

这个题目跟之前做的有一定区别，之前做的大多是表示一个序列的转移矩阵（用一列 列向量表示一个序列的几项）

而这个题给出了 an 的转移关系 bn的转移关系 要求 an*bn的前n项和

应当扩充列的范围（矩阵表达的含义增加）

【An Bn An*Bn Sum(n)】  转移关系是很好列的，剩下的就是矩阵快速幂

*/

LL n, a0, ax, ay, b0, bx, by;

struct Mat

{

    LL a[][];

    Mat()

    {

        memset(a, , sizeof(a));

    }

    Mat operator*(const Mat& rhs)

    {

        Mat ret;

        for (int i = ; i < ; i++)

        {

            for (int j = ; j < ; j++)

            {

                if(a[i][j])

                {

                    for (int k = ; k < ; k++)

                    {

                        ret.a[i][k] = (ret.a[i][k] + a[i][j] * rhs.a[j][k]) % MOD;

                    }

                }

            }

        }

        return ret;

    }

};

Mat fpow(Mat m, LL b)

{

    Mat ans;

    for (int i = ; i < ; i++)

        ans.a[i][i] = ;

    while (b != )

    {

        if (b & )

            ans = m * ans;

        m = m * m;

        b = b / ;

    }

    return ans;

}

int main()

{

    while (scanf("%lld", &n) != EOF)

    {

        scanf("%lld%lld%lld%lld%lld%lld", &a0, &ax, &ay, &b0, &bx, &by);

        if (n == )

        {

            printf("0\n");

            continue;

        }

        Mat M;

        M.a[][] = ax%MOD, M.a[][] = ax%MOD*by%MOD, M.a[][] = ax%MOD*by%MOD;

        M.a[][] = bx%MOD, M.a[][] = M.a[][] = bx%MOD*ay%MOD;

        M.a[][] = M.a[][] = ax%MOD*bx%MOD;

        M.a[][] = ;

        M.a[][] = ay%MOD, M.a[][] = by%MOD, M.a[][] = M.a[][] = ay%MOD*by%MOD, M.a[][] = ;

        if (n == )

            printf("%lld\n", a0*b0%MOD);

        else

        {

            M = fpow(M, n - );

            LL ans = ;

            ans = (ans + a0*M.a[][] % MOD) % MOD;

            ans = (ans + b0*M.a[][] % MOD) % MOD;

            ans = (ans + +a0%MOD*b0%MOD*M.a[][] % MOD) % MOD;

            ans = (ans + a0%MOD*b0%MOD*M.a[][] % MOD) % MOD;

            ans = (ans +M.a[][] % MOD) % MOD;

            printf("%lld\n", ans);

        }

    }

}