#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void hehe(int rez[][2], int a[2][2], int b[2][2])
{
rez[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
rez[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
rez[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
rez[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
}
void inm(int z[][2], int m[2][2], int k)
{
int i = 1, w = k;
while (w > 1)
{
i = i << 1;
w = w >> 1;
}
int rez[2][2] = {{0,0},{0,0}};
i = i >> 1;
while (i != 0)
{
hehe(rez,z,z);
printf("rez\n%i %i\n%i %i\n\n", rez[0][0], rez[0][1], rez[1][0], rez[1][1]);
memcpy(z,rez,4 * sizeof(int));
if (k & i)
{
hehe(rez, z, m);
memcpy(z,rez,4 * sizeof(int));
}
printf("%i %i\n%i %i\n\n", z[0][0], z[0][1], z[1][0], z[1][1]);
i = i >> 1;
}
}
int main()
{
FILE * f = fopen("kfib.in", "r");
int k;
fscanf(f, "%i", &k);
fclose(f);
int z[2][2] = {{0, 1}, {1, 1}};
int m[2][2] = {{0, 1}, {1, 1}};
f = fopen("kfib.out", "w");
if (k == 0 || k == 1)
;//fprintf(f, "%i", k == 1 ? 1 : 0);
else
{
inm(z, m, k-1);
fprintf(f, "%i", z[1][1]);
}
fclose(f);
return 0;
}