// Quick Pow Function with Mod & Matrix Quick Pow with Mod Template (C++ Version)
// By meowjiao
// Include headers
#include <cstring>
// Include other headers there
#include <...>
// Use namespace
using namespace ...;
// Mod
const long long mod = 1000000007;
// QuickPow Function
long long qpow(long long a, long long b, long long mod) {
a %= mod;
long long ans = 1;
while (b) {
if (b & 1) {
ans = (ans * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
// Matrix Quick Pow Struct
struct Matrix {
int n,m,a[4][4];
Matrix() {
n = m = 0;
memset(a,0,sizeof(a));
}
Matrix(int x,int y) {
n = x;
m = y;
memset(a,0,sizeof(a));
}
Matrix(int x) {
n = m = x;
memset(a,0,sizeof(a));
for (int i = 0;i < n;i++) {
a[i][i] = 1;
}
}
Matrix operator+(const Matrix &b) const {
Matrix c(n,m);
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
c.a[i][j] = ((long long)a[i][j] + b.a[i][j]) % mod;
}
}
return c;
}
Matrix operator+=(const Matrix &b) {
return *this = *this + b;
}
Matrix operator*(const Matrix &b) const {
Matrix c(n,b.m);
for (int i = 0;i < n;i++) {
for (int j = 0;j < b.m;j++) {
for (int k = 0;k < m;k++) {
c.a[i][j] = ((((long long)a[i][k] * b.a[k][j]) % mod) + c.a[i][j]) % mod;
}
}
}
return c;
}
Matrix operator*=(const Matrix &b) {
return *this = *this * b;
}
Matrix operator^(long long k) {
Matrix t = *this,ans(n);
while (k) {
if (k & 1) {
ans *= t;
}
t *= t;
k >>= 1;
}
return ans;
}
Matrix operator^=(long long k) {
return *this = *this ^ k;
}
};
// Main Function
int main() {
// Do sometings there
return 0;
}
