#include <errno.h>
#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
	if (argc != 2) {
		fprintf(stderr, "usage: %s <count>\n", argv[0]);
		exit(-1);
	}

	char *end = argv[1];
	long count = strtol(argv[1], &end, 10);
	if (argv[1] == end || *end) {
		fprintf(stderr, "usage: %s <count>\n", argv[0]);
		exit(-1);
	} else if (errno == ERANGE) {
		perror(argv[1]);
		exit(-1);
	}

	mpz_t a, b, p, q;
	mpz_t ta, tp, tmp;
	mpz_init_set_ui(a, 1);
	mpz_init_set_ui(b, 0);
	mpz_init_set_ui(p, 0);
	mpz_init_set_ui(q, 1);
	mpz_init(tmp);
	mpz_init(ta);
	mpz_init(tp);

	while (count > 0) {
		if (count % 2 == 0) {
			mpz_mul(tmp, p, p);
			mpz_addmul(tp, q, q);

			mpz_mul(tmp, p, q);
			mpz_mul_ui(tmp, tmp, 2);
			mpz_add(q, tmp, q);
			mpz_set(p, tp);

			count /= 2;
		} else {
			mpz_mul(tmp, b, q);
			mpz_addmul(tmp, a, q);
			mpz_addmul(tmp, a, p);
			mpz_set(ta, tmp);

			mpz_set_ui(tmp, 0);
			mpz_addmul(tmp, b, p);
			mpz_addmul(tmp, a, q);
			mpz_set(a, ta);
			mpz_set(b, tmp);

			count -= 1;
		}
	}

	//mpz_out_str(stdout, 10, b);
	//printf("\n");
}