Pagini recente » Cod sursa (job #393205) | Cod sursa (job #2290947) | Cod sursa (job #1144398) | Cod sursa (job #888528) | Cod sursa (job #2187097)
#include <cstdio>
using namespace std;
int k;
long long fib[4][4]={{0, 0, 0}, {0, 1, 1}, {0, 0 ,0}};
long long a[4][4]={{0, 0, 0}, {0, 1, 1}, {0, 1, 0}};
long long cop[4][4];
const int MOD=666013;
void inmultire(long long fibx[4][4], long long ax[4][4], long long copx[4][4])
{
for(int i=1; i<=2; i++)
{
for(int j=1; j<=2; j++)
{
for(int k=1; k<=2; k++)
{
copx[i][j]=(copx[i][j]+(1LL*(fibx[i][k]*ax[k][j])))%MOD;
}
}
}
}
void copiere(long long fibx[4][4], long long copx[4][4])
{
for(int i=1; i<=2; i++)
for(int j=1; j<=2; j++)
{
fibx[i][j]=copx[i][j];
copx[i][j]=0;
}
}
void put(int n)
{
while(n)
{
if(n%2 == 1)
{
n--;
inmultire(fib, a, cop);
copiere(fib, cop);
continue;
}
n/=2;
inmultire(a, a, cop);
copiere(a, cop);
}
}
int main()
{
freopen("kfib.in", "r", stdin);
freopen("kfib.out", "w", stdout);
scanf("%d", &k);
put(k-2);
//int s=(fib[1][1]+fib[1][2])%MOD;
printf("%d", (1LL*fib[1][1]+fib[2][1])%MOD);
return 0;
}