Cod sursa(job #719049)
#include<fstream>
#include <cstring>
using namespace std;
#define mod 666013
int mat[2][2], sol[2][2];
void matrix(int a[][2], int b[][2], int c[][2])
{
int i,j,k;
for(i=0;i<2;++i)
for(j=0;j<2;++j)
for(k=0;k<2;++k)
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
}
void lg_power(int p)
{
mat[0][1]=mat[1][0]=mat[1][1]=1;
int c[2][2], aux[2][2];
memcpy(c,mat,sizeof(mat));
for(;p;p>>=1)
{
if(p&1)
{
memset(aux,0,sizeof(aux));
matrix(mat,c,aux);
memcpy(mat,aux,sizeof(aux));
}
memset(aux,0,sizeof(aux));
matrix(c,c,aux);
memcpy(c,aux,sizeof(c));
}
}
int main()
{
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int k;
fin>>k;
lg_power(k-1);
fout<<mat[1][0];
}