Cod sursa(job #720788)
#include<cstdio>
#include<cstring>
#define modulo 666013
using namespace std;
int m[3][3],a[3][3],aux[3][3];
void inm (int a[][3], int b[][3], int c[][3])
{
for (int i=1; i<=2; i++)
for (int j=1; j<=2; j++)
for (int k=1; k<=2; k++)
c[i][j]=(c[i][j] + (long long) a[i][k] * b[k][j])%modulo;
}
int main ()
{
int n;
freopen("kfib.in","r",stdin);
freopen("kfib.out","w",stdout);
scanf("%d",&n);
a[1][2]=a[2][1]=a[2][2]=1;
m[1][2]=m[2][1]=m[2][2]=1;
n--;
while (n)
{
if (n%2)
{
memset(aux,0,sizeof(aux));
inm(m,a,aux);
memcpy(m,aux,sizeof(aux));
}
memset(aux,0,sizeof(aux));
inm(a,a,aux);
memcpy(a,aux,sizeof(aux));
n/=2;
}
printf("%d",m[1][2]);
return 0;
}