// Quick Pow Function with Mod & Matrix Quick Pow with Mod Struct (C++ Version)
// MIT License
// By meowjiao
// [Your Name] use on [Date and Time]
// Include files
#include <cstring>
// Include other files 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) {
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;
long long a[N][N];
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 = 1;i <= n;i++) {
a[i][i] = 1;
}
}
Matrix operator*(const Matrix &b) const {
Matrix c(n,b.m);
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= b.m;j++) {
for (int k = 1;k <= m;k++) {
c.a[i][j] = (c.a[i][j] + (a[i][k] * b.a[k][j]) % mod) % mod;
}
}
}
return c;
}
Matrix operator*=(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;
}
