Problem Description

An Arc of Dream is a curve defined by following function:

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

 

Input

There 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⁹.

 

Output

For each test case, output AoD(N) modulo 1,000,000,007.

 

Sample Input

 

Sample Output

 

Author

Zejun Wu (watashi)

 

Source

 

Recommend

zhuyuanchen520

 

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod=;

struct Matrix{

    long long arr[][];

};

Matrix init,unit;

long long n,a0,ax,ay,b0,bx,by;  //注意用long long，否则会溢出

Matrix Mul(Matrix a,Matrix b){

    Matrix c;

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

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

            c.arr[i][j]=;

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

                c.arr[i][j]=(c.arr[i][j]+a.arr[i][k]*b.arr[k][j]%mod)%mod;

            c.arr[i][j]%=mod;

        }

    return c;

}

Matrix Pow(Matrix a,Matrix b,long long k){

    while(k){

        if(k&){

            b=Mul(b,a);

        }

        a=Mul(a,a);

        k>>=;

    }

    return b;

}

void Init(){

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

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

            init.arr[i][j]=;

            unit.arr[i][j]=;

        }

    unit.arr[][]=,   unit.arr[][]=a0%mod,    unit.arr[][]=b0%mod,    unit.arr[][]=a0*b0%mod,

    unit.arr[][]=a0*b0%mod;

    init.arr[][]=,   init.arr[][]=ay%mod,    init.arr[][]=by%mod,    init.arr[][]=ay*by%mod,

    init.arr[][]=ay*by%mod,   init.arr[][]=ax%mod,  init.arr[][]=ax*by%mod,   init.arr[][]=ax*by%mod,

    init.arr[][]=bx%mod,  init.arr[][]=ay*bx%mod,   init.arr[][]=ay*bx%mod,   init.arr[][]=ax*bx%mod,

    init.arr[][]=ax*bx%mod,   init.arr[][]=;

}

int main(){

    //freopen("input.txt","r",stdin);

    while(cin>>n){

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

        cin>>a0>>ax>>ay>>b0>>bx>>by;

        if(n==){

            puts("");

            continue;

        }

        Init();

        Matrix ans=Pow(init,unit,n-);

        cout<<ans.arr[][]<<endl;

    }

    return ;

}