## Editorial for Trò chơi lò cò

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của happyboy99x

#include <bits/stdc++.h>
using namespace std;

int modulo;

vector<vector<int> > multiply(const vector<vector<int> > &a, const vector<vector<int> > &b) {
vector<vector<int> > c (a.size(), vector<int>(b[0].size()));
for (int i = 0; i < (int) a.size(); ++i) {
for (int j = 0; j < (int) a[0].size(); ++j) {
for (int k = 0; k < (int) b[0].size(); ++k) {
c[i][k] = (c[i][k] + a[i][j] * b[j][k]) % modulo;
}
}
}
return c;
}

vector<vector<int> > unit(int n) {
vector<vector<int> > a (n, vector<int>(n));
for (int i = 0; i < n; ++i) a[i][i] = 1;
return a;
}

vector<vector<int> > power(vector<vector<int> > a, long long n) {
vector<vector<int> > result = unit(a.size());
while (n > 0) {
if (n % 2 != 0) result = multiply(result, a);
a = multiply(a, a);
n /= 2;
}
return result;
}

int main() {
ios::sync_with_stdio(false);
long long n; cin >> n >> modulo;
vector<vector<int> > first (3, vector<int>(1));
first[2][0] = 1;
vector<vector<int> > base (3, vector<int>(3));
base[0][1] = base[1][2] = base[2][0] = base[2][1] = base[2][2] = 1;
cout << multiply(power(base, n), first)[2][0] << '\n';
return 0;
}


#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define FORD(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

using namespace std;

struct matrix { long long a[3][3]; };

int MOD;
long long n;
matrix base;

matrix operator * (matrix a, matrix b) {
matrix c;
FOR(i, 0, 3) FOR(j, 0, 3) {
c.a[i][j] = 0;
FOR(k, 0, 3)
c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j]) % MOD;
}
return c;
}

matrix power(long long p) {
if (p == 1) return base;
matrix x = power(p >> 1);
x = x * x;
if (p & 1) return x * base;
return x;
}

int main() {
ios::sync_with_stdio(0); cin.tie(0);
freopen("DHLOCO.in", "r", stdin);
cin >> n >> MOD;
base.a[0][0] = base.a[0][1] = base.a[0][2] = base.a[1][0] = base.a[2][1] = 1;
long long f[4];
f[1] = 1; f[2] = 2; f[3] = 4;
if (n <= 3) {
cout << f[n] % MOD << endl;
} else {
matrix M = power(n - 3);
cout << (f[3] * M.a[0][0] + f[2] * M.a[0][1] + f[1] * M.a[0][2]) % MOD << endl;
}
return 0;
}


#### Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
const int sta[]={1,1,2,4};
const int tmp[][3]={{0,0,1},{1,0,1},{0,1,1}};
int mod;
struct Matrix {
int m,n;
vector<vector<int> > d;
Matrix() {
m=n=0;
d.clear();
}
Matrix(int m,int n) {
this->m=m;
this->n=n;
d.assign(m,vector<int>(n,0));
}
Matrix operator * (const Matrix &a) const {
int x=m;
int y=n;
int z=a.n;
Matrix res(x,z);
REP(i,x) REP(j,y) REP(k,z) res.d[i][k]=(res.d[i][k]+d[i][j]*a.d[j][k])%mod;
return (res);
}
Matrix operator ^ (long long k) const {
Matrix res(n,n);
Matrix mul=*this;
REP(i,n) REP(j,n) res.d[i][j]=i==j;
while (k>0) {
if (k&1) res=res*mul;
mul=mul*mul;
k>>=1;
}
return (res);
}
};
void process(void) {
long long n;
cin>>n>>mod;
Matrix fst(1,3),mul(3,3);
REP(i,3) fst.d[0][i]=sta[i];
REP(i,3) REP(j,3) mul.d[i][j]=tmp[i][j];
fst=fst*(mul^n);
cout<<fst.d[0][0]<<endl;
}
int main(void) {
ios::sync_with_stdio(true);
process();
return 0;
}