HDU 4686 Arc of Dream

Problem Description

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

where

a

0 = A0

a

i = a

i-1*AX+AY

b

0 = 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

18, and all the other integers are no more than 2×10

9.

Output

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

Sample Input

1

1 2 3

4 5 6

2

1 2 3

4 5 6

3

1 2 3

4 5 6

Sample Output

4

134

1902

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
const ll size=6;
ll a0,b0,ax,bx,ay,by,n;

struct abc
{
    ll a[size][size];
    abc(){ memset(a,0,sizeof(a));};
};

abc operator *(const abc &a,const abc &b)
{
    abc c;
    for (int i=1;i<size;i++)
        for (int j=1;j<size;j++)
            for (int k=1;k<size;k++)
            {
                (c.a[i][k]+=a.a[i][j]*b.a[j][k])%=M;
                (c.a[i][k]+=M)%=M;
            }
    return c;
}

int main(){
  while (cin>>n>>a0>>ax>>ay>>b0>>bx>>by)
  {
     if (n==0) {puts("0"); continue;}
     abc r,A;
     r.a[1][2]=(a0*ax+ay)%M;
     r.a[1][3]=(b0*bx+by)%M;
     r.a[1][1]=(r.a[1][2]*r.a[1][3])%M;
     r.a[1][4]=1;
     r.a[1][5]=(a0*b0)%M;
     A.a[1][1]=(ax*bx)%M;
     A.a[1][5]=1;
     A.a[2][1]=(ax*by)%M;
     A.a[2][2]=ax%M;
     A.a[3][1]=(ay*bx)%M;
     A.a[3][3]=bx%M;
     A.a[4][1]=(ay*by)%M;
     A.a[4][2]=ay%M;
     A.a[4][3]=by%M;
     A.a[4][4]=1;
     A.a[5][5]=1;
     for (--n;n>0;n>>=1)
     {
         if (n&1) r=r*A;
         A=A*A;
     }
     cout<<r.a[1][5]<<endl;
  }
  return 0;
}