Untitled

unknown
c_cpp
14 days ago
1.6 kB
13
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;

const int mod = 1e9 + 7;
int add(int x, int y) { return (x + y) % mod; }
int sub(int x, int y) { return (x - y + mod) % mod; }
int mul(int x, int y) { return (x * 1LL * y) % mod; }
int modpow(int n, int k) {
int res = 1;
while (k) {
if (k & 1) res = mul(res, n);
n = mul(n, n);
k >>= 1;
}
return res;
}
int divide(int a, int b) { return mul(a, modpow(b, mod - 2)); }

vector<vector<int>> mul(const vector<vector<int>>& a, const vector<vector<int>>& b) {
int n = a.size(), m = b[0].size();
vector<vector<int>> c(n, vector<int>(m));
int r = a[0].size();
assert(r == (int)b.size());

for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int k = 0; k < r; k++)

return c;
}

void solve() {
ll n;
cin >> n;

vector<vector<int>> mat(5, vector<int>(5));
for (int i = 0; i < 4; i++)
for (int k = 0; k < 4; k++) if (k != i) mat[i][k] = 1;
mat[4][3] = mat[4][4] = 1;

vector<vector<int>> a(5, vector<int>(5));
for (int i = 0; i < 5; i++) a[i][i] = 1;

vector<vector<int>> fin(5, vector<int>(1));
fin[3][0] = 1;
n += 1;
while (n) {
if (n & 1) a = mul(a, mat);
mat = mul(mat, mat);
n >>= 1;
}
a = mul(a, fin);
cout << sub(a[4][0], 1) << "\n";
}

int main() {
ios::sync_with_stdio(0); cin.tie(0);
tt = 1, tc = 1; // cin >> tt;
while (tt--) solve(), tc++;
}