Online C++ Compiler

#include <iostream> using namespace std; #define MOD 1000000009 long calcNthTerm(long n) { if (n <= 1) return 1; n--; long resultantMat[2][2] = { 1, 0, 0, 1 }; long transMat[2][2] = { 2, 3, 1, 0 }; while (n) { long tempMat[2][2]; if (n & 1) { tempMat[0][0] = (resultantMat[0][0] * transMat[0][0] + resultantMat[0][1] * transMat[1][0]) % MOD; tempMat[0][1] = (resultantMat[0][0] * transMat[0][1] + resultantMat[0][1] * transMat[1][1]) % MOD; tempMat[1][0] = (resultantMat[1][0] * transMat[0][0] + resultantMat[1][1] * transMat[1][0]) % MOD; tempMat[1][1] = (resultantMat[1][0] * transMat[0][1] + resultantMat[1][1] * transMat[1][1]) % MOD; resultantMat[0][0] = tempMat[0][0]; resultantMat[0][1] = tempMat[0][1]; resultantMat[1][0] = tempMat[1][0]; resultantMat[1][1] = tempMat[1][1]; } n = n / 2; tempMat[0][0] = (transMat[0][0] * transMat[0][0] + transMat[0][1] * transMat[1][0]) % MOD; tempMat[0][1] = (transMat[0][0] * transMat[0][1] + transMat[0][1] * transMat[1][1]) % MOD; tempMat[1][0] = (transMat[1][0] * transMat[0][0] + transMat[1][1] * transMat[1][0]) % MOD; tempMat[1][1] = (transMat[1][0] * transMat[0][1] + transMat[1][1] * transMat[1][1]) % MOD; transMat[0][0] = tempMat[0][0]; transMat[0][1] = tempMat[0][1]; transMat[1][0] = tempMat[1][0]; transMat[1][1] = tempMat[1][1]; } return (resultantMat[0][0] * 1 + resultantMat[0][1] * 1) % MOD; } int main() { long n = 5; cout<<n<<"th term of found using matrix exponentiation is "<<calcNthTerm(n); return 0; }