【cf 1182 E】Product Oriented Recurrence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
#pragma warning(disable:4996)
struct Sarray {
  static const ll mod = 1e9 + 6;
  static const ll LEN = 3;
  ll len, data[LEN][LEN];

  Sarray(ll len, ll flag) :len(len) {
    for (ll i = 0; i < len; i++) {
      for (ll j = 0; j < len; j++)data[i][j] = 0;
      data[i][i] = flag;
    }
  }

  Sarray operator *(const Sarray&a) {
    Sarray tem(a.len, 0);
    for (ll i = 0; i < len; i++) {
      for (ll j = 0; j < len; j++) {
        for (ll k = 0; k < len; k++) {
          tem.data[i][j] = (tem.data[i][j] + data[i][k] * a.data[k][j]) % mod;
        }
      }
    }
    return tem;
  }

  Sarray operator +(const Sarray&a) {
    Sarray tem(a.len, 0);
    for (ll i = 0; i < len; i++) {
      for (ll j = 0; j < len; j++) {
        tem.data[i][j] = (data[i][j] + a.data[i][j]) % mod;
      }
    }
    return tem;
  }
};

Sarray qpow(Sarray a, ll b) 
{
  Sarray tem(a.len, 1);
  while (b) {
    if (b & 1)tem = a * tem;
    a = a * a;
    b >>= 1;
  }
  return tem;
}

ll qpow(ll a, ll b) {
  ll ret = 1;
  while (b) {
    if (b & 1) ret = ret * a%mod;
    a = a * a%mod;
    b >>= 1;
  }
  return ret;
}
ll inita[3][3] =
{
  0,0,0,
  0,0,0,
  1,0,0
};

ll initb[3][3] =
{
  0,0,0,
  1,0,0,
  0,0,0
};
ll initc[3][3] =
{
  1,0,0,
  0,0,0,
  0,0,0
};
ll trans[3][3] =
{
  1,1,1,
  1,0,0,
  0,1,0
};

ll getPon(ll n, ll beg[3][3]) {
  Sarray orn(3, 1), trans1(3, 1);
  memcpy(orn.data, beg, sizeof(orn.data));
  memcpy(trans1.data, trans, sizeof(trans1.data));
  if (n == 1) return beg[2][0];
  if (n == 2) return beg[1][0];
  return (qpow(trans1, n - 3)*orn).data[0][0];
}
int main()
{
  ll n, f1, f2, f3, c;
  while (cin >> n >> f1 >> f2 >> f3 >> c)
  {
    ll g1 = f1 * c%mod;
    ll g2 = f2 * c%mod*c%mod;
    ll g3 = f3 * c%mod*c%mod*c%mod;
    
    ll ponmod = mod - 1;

    //指數取模
    ll A = getPon(n, inita)%ponmod;
    ll B = getPon(n, initb)%ponmod;
    ll C = getPon(n, initc)%ponmod;


    ll gn = qpow(g1, A)*qpow(g2, B) % mod*qpow(g3, C) % mod;
    
    //找一下逆元
    ll cn = qpow(c, n);
    ll inv = qpow(cn, mod - 2);
    ll ans = gn * inv%mod;

    cout << ans << endl;
  }
}