void multiply(long long a[3][3], long long b[3][3])
{
// Creating an auxiliary matrix to store elements
// of the multiplication matrix
long long mul[3][3];
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
mul[i][j] = 0;
for (int k = 0; k < 3; k++)
mul[i][j] += a[i][k]*b[k][j];
}
}// storing the multiplication result in a[][]
for (int i=0; i<3; i++)
for (int j=0; j<3; j++)
a[i][j] = modulo(mul[i][j], NUM); // Updating our matrix
}long long power(long long F[3][3], long long n)
{
/**
| 1 2 1 |
| 1 0 0 |
| 0 1 0 |
**/
long long M[3][3] = {{1,2,1}, {1,0,0}, {0,1,0}};
long long A[3][3] = {{1,2,1}, {1,0,0}, {0,1,0}};// Multiply it with initial values i.e with
// F(0) = 0, F(1) = 1, F(2) = 1
if (n==1)
return F[0][0]*13 + F[0][1]*12+F[0][2]*1;power(F, n/2);multiply(F, F);if (n%2 != 0)
multiply(F, M);// Multiply it with initial values i.e with
// F(0) = 0, F(1) = 1, F(2) = 1return F[0][0]*13 + F[0][1]*12+F[0][2]*1;// Multiply it with initial values i.e with
// F(0) = 0, F(1) = 1, F(2) = 1}long long findNthTerm(long long n)
{long long F[3][3] = {{1,2,1}, {1,0,0}, {0,1,0}} ;//n need>3
if(n==1)
return 1;
if(n==2)
return 12;
if(n==3)
return 13;return power(F, n-3);
/**
| F(n) | = [ | 1 2 1 | ] ^(n-3)*| F(3) |
| F(n-1) | [ | 1 0 0 | ] | F(2) |
| F(n-2) | [ | 0 1 0 | ] | F(1) |
**/
}...modulo(findNthTerm(x),NUM)
https://www.geeksforgeeks.org/matrix-exponentiation/
