#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
using namespace std;
 
 
class BigInt{
	// Array with the parts of the big integer in little endian
	vector<int> value;
	int base;
	void add_most_significant(int);
	void add_most_significant_otherbig(BigInt*, int);
	public:
		BigInt(int begin=0, int _base=100): value({begin}), base(_base){ };
		BigInt(BigInt& other): value(other.value), base(other.base){ };
		~BigInt(){ };
		void add(int);
		void addBig(BigInt*);
		void print(ostream& output) const;
		static BigInt* fibonacci(int);
};
 
void BigInt::add_most_significant_otherbig(BigInt* other, int m){
	int carry = m, sum;
	for(int i = value.size(); i < other->value.size(); ++i){
		sum = other->value[i] + carry;
		value.push_back(sum % base);
		carry = sum/base;
	}
	while(carry){
		value.push_back(carry % base); 
		carry /= base;
	}
}
 
void BigInt::add(int a){
	int sum = 0, carry = a;
	for(int i = 0; i < value.size(); i++){
		sum = value[i] + carry;
		value[i] = sum % base;
		carry = sum/base;
	}
	if (carry)
		add_most_significant(carry);
}
 
void BigInt::add_most_significant(int m){
	int carry = m;
	while(carry){
		value.push_back(carry % base); 
		carry /= base;
	}
}
 
void BigInt::addBig(BigInt* other){
	if(base != other->base){ 	// Won't work if they have different base
		cerr << "Addition of BigInt objects with different base not implemented yet!" << endl;
		exit(1);
	}
	int sum = 0, carry = 0, i;
	for(i = 0; i < value.size() && i < other->value.size(); ++i){
		sum = value[i] + other->value[i] + carry;
		value[i] = sum % base;
		carry = sum/base;
	}
	for(; i < value.size() && carry;++i){
		sum = value[i] + carry;
		value[i] = sum % base;
		carry = sum/base;
	}
	add_most_significant_otherbig(other, carry);
}
 
ostream& operator<<(ostream& output, const BigInt bigint){
	bigint.print(output);
	return output;
}
 
void BigInt::print(ostream& output) const {
	// string of the format depends on the "size" of the base (trailing 0 in format => fill with zeros if needed when printing)
	int l_base = to_string(base-1).length();
	string format("%0" + to_string(l_base) + "d");
 
	// Begin with the most significant part: outside the loop because it doesn't need trailing zeros
	output << value[value.size() - 1];
	char* buf = new char[l_base+1];
	for(int i = value.size() - 2; i >= 0; i-- ){
		sprintf(buf, format.c_str(), value[i]);
		output << buf;
	}
	delete[] buf;
}
 
BigInt* BigInt::fibonacci(int n){
	if( n <= 0){
		return new BigInt(0);
	}
 
	BigInt* previous[] = {new BigInt(0), new BigInt(1)};
	for(int i = 2; i <= n; ++i){
		previous[i&1]->addBig(previous[(i-1)&1]);
	}
	//Result is in previous[i&1]
	// but first delete the other one: previous[!(i&1)]  -> ! will turn 0 into 1 and 1 into 0
	delete previous[!(n&1)];
 
	return previous[n&1];
}
 
int main() {
	int n = 10000;
	BigInt* bigint = BigInt::fibonacci(n);
	cout << *bigint << endl;
	delete bigint;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgpjbGFzcyBCaWdJbnR7CgkvLyBBcnJheSB3aXRoIHRoZSBwYXJ0cyBvZiB0aGUgYmlnIGludGVnZXIgaW4gbGl0dGxlIGVuZGlhbgoJdmVjdG9yPGludD4gdmFsdWU7CglpbnQgYmFzZTsKCXZvaWQgYWRkX21vc3Rfc2lnbmlmaWNhbnQoaW50KTsKCXZvaWQgYWRkX21vc3Rfc2lnbmlmaWNhbnRfb3RoZXJiaWcoQmlnSW50KiwgaW50KTsKCXB1YmxpYzoKCQlCaWdJbnQoaW50IGJlZ2luPTAsIGludCBfYmFzZT0xMDApOiB2YWx1ZSh7YmVnaW59KSwgYmFzZShfYmFzZSl7IH07CgkJQmlnSW50KEJpZ0ludCYgb3RoZXIpOiB2YWx1ZShvdGhlci52YWx1ZSksIGJhc2Uob3RoZXIuYmFzZSl7IH07CgkJfkJpZ0ludCgpeyB9OwoJCXZvaWQgYWRkKGludCk7CgkJdm9pZCBhZGRCaWcoQmlnSW50Kik7CgkJdm9pZCBwcmludChvc3RyZWFtJiBvdXRwdXQpIGNvbnN0OwoJCXN0YXRpYyBCaWdJbnQqIGZpYm9uYWNjaShpbnQpOwp9OwoKdm9pZCBCaWdJbnQ6OmFkZF9tb3N0X3NpZ25pZmljYW50X290aGVyYmlnKEJpZ0ludCogb3RoZXIsIGludCBtKXsKCWludCBjYXJyeSA9IG0sIHN1bTsKCWZvcihpbnQgaSA9IHZhbHVlLnNpemUoKTsgaSA8IG90aGVyLT52YWx1ZS5zaXplKCk7ICsraSl7CgkJc3VtID0gb3RoZXItPnZhbHVlW2ldICsgY2Fycnk7CgkJdmFsdWUucHVzaF9iYWNrKHN1bSAlIGJhc2UpOwoJCWNhcnJ5ID0gc3VtL2Jhc2U7Cgl9Cgl3aGlsZShjYXJyeSl7CgkJdmFsdWUucHVzaF9iYWNrKGNhcnJ5ICUgYmFzZSk7IAoJCWNhcnJ5IC89IGJhc2U7Cgl9Cn0KCnZvaWQgQmlnSW50OjphZGQoaW50IGEpewoJaW50IHN1bSA9IDAsIGNhcnJ5ID0gYTsKCWZvcihpbnQgaSA9IDA7IGkgPCB2YWx1ZS5zaXplKCk7IGkrKyl7CgkJc3VtID0gdmFsdWVbaV0gKyBjYXJyeTsKCQl2YWx1ZVtpXSA9IHN1bSAlIGJhc2U7CgkJY2FycnkgPSBzdW0vYmFzZTsKCX0KCWlmIChjYXJyeSkKCQlhZGRfbW9zdF9zaWduaWZpY2FudChjYXJyeSk7Cn0KCnZvaWQgQmlnSW50OjphZGRfbW9zdF9zaWduaWZpY2FudChpbnQgbSl7CglpbnQgY2FycnkgPSBtOwoJd2hpbGUoY2FycnkpewoJCXZhbHVlLnB1c2hfYmFjayhjYXJyeSAlIGJhc2UpOyAKCQljYXJyeSAvPSBiYXNlOwoJfQp9Cgp2b2lkIEJpZ0ludDo6YWRkQmlnKEJpZ0ludCogb3RoZXIpewoJaWYoYmFzZSAhPSBvdGhlci0+YmFzZSl7IAkvLyBXb24ndCB3b3JrIGlmIHRoZXkgaGF2ZSBkaWZmZXJlbnQgYmFzZQoJCWNlcnIgPDwgIkFkZGl0aW9uIG9mIEJpZ0ludCBvYmplY3RzIHdpdGggZGlmZmVyZW50IGJhc2Ugbm90IGltcGxlbWVudGVkIHlldCEiIDw8IGVuZGw7CgkJZXhpdCgxKTsKCX0KCWludCBzdW0gPSAwLCBjYXJyeSA9IDAsIGk7Cglmb3IoaSA9IDA7IGkgPCB2YWx1ZS5zaXplKCkgJiYgaSA8IG90aGVyLT52YWx1ZS5zaXplKCk7ICsraSl7CgkJc3VtID0gdmFsdWVbaV0gKyBvdGhlci0+dmFsdWVbaV0gKyBjYXJyeTsKCQl2YWx1ZVtpXSA9IHN1bSAlIGJhc2U7CgkJY2FycnkgPSBzdW0vYmFzZTsKCX0KCWZvcig7IGkgPCB2YWx1ZS5zaXplKCkgJiYgY2Fycnk7KytpKXsKCQlzdW0gPSB2YWx1ZVtpXSArIGNhcnJ5OwoJCXZhbHVlW2ldID0gc3VtICUgYmFzZTsKCQljYXJyeSA9IHN1bS9iYXNlOwoJfQoJYWRkX21vc3Rfc2lnbmlmaWNhbnRfb3RoZXJiaWcob3RoZXIsIGNhcnJ5KTsKfQoKb3N0cmVhbSYgb3BlcmF0b3I8PChvc3RyZWFtJiBvdXRwdXQsIGNvbnN0IEJpZ0ludCBiaWdpbnQpewoJYmlnaW50LnByaW50KG91dHB1dCk7CglyZXR1cm4gb3V0cHV0Owp9Cgp2b2lkIEJpZ0ludDo6cHJpbnQob3N0cmVhbSYgb3V0cHV0KSBjb25zdCB7CgkvLyBzdHJpbmcgb2YgdGhlIGZvcm1hdCBkZXBlbmRzIG9uIHRoZSAic2l6ZSIgb2YgdGhlIGJhc2UgKHRyYWlsaW5nIDAgaW4gZm9ybWF0ID0+IGZpbGwgd2l0aCB6ZXJvcyBpZiBuZWVkZWQgd2hlbiBwcmludGluZykKCWludCBsX2Jhc2UgPSB0b19zdHJpbmcoYmFzZS0xKS5sZW5ndGgoKTsKCXN0cmluZyBmb3JtYXQoIiUwIiArIHRvX3N0cmluZyhsX2Jhc2UpICsgImQiKTsKCQoJLy8gQmVnaW4gd2l0aCB0aGUgbW9zdCBzaWduaWZpY2FudCBwYXJ0OiBvdXRzaWRlIHRoZSBsb29wIGJlY2F1c2UgaXQgZG9lc24ndCBuZWVkIHRyYWlsaW5nIHplcm9zCglvdXRwdXQgPDwgdmFsdWVbdmFsdWUuc2l6ZSgpIC0gMV07CgljaGFyKiBidWYgPSBuZXcgY2hhcltsX2Jhc2UrMV07Cglmb3IoaW50IGkgPSB2YWx1ZS5zaXplKCkgLSAyOyBpID49IDA7IGktLSApewoJCXNwcmludGYoYnVmLCBmb3JtYXQuY19zdHIoKSwgdmFsdWVbaV0pOwoJCW91dHB1dCA8PCBidWY7Cgl9CglkZWxldGVbXSBidWY7Cn0KCkJpZ0ludCogQmlnSW50OjpmaWJvbmFjY2koaW50IG4pewoJaWYoIG4gPD0gMCl7CgkJcmV0dXJuIG5ldyBCaWdJbnQoMCk7Cgl9CgoJQmlnSW50KiBwcmV2aW91c1tdID0ge25ldyBCaWdJbnQoMCksIG5ldyBCaWdJbnQoMSl9OwoJZm9yKGludCBpID0gMjsgaSA8PSBuOyArK2kpewoJCXByZXZpb3VzW2kmMV0tPmFkZEJpZyhwcmV2aW91c1soaS0xKSYxXSk7Cgl9CgkvL1Jlc3VsdCBpcyBpbiBwcmV2aW91c1tpJjFdCgkvLyBidXQgZmlyc3QgZGVsZXRlIHRoZSBvdGhlciBvbmU6IHByZXZpb3VzWyEoaSYxKV0gIC0+ICEgd2lsbCB0dXJuIDAgaW50byAxIGFuZCAxIGludG8gMAoJZGVsZXRlIHByZXZpb3VzWyEobiYxKV07CgoJcmV0dXJuIHByZXZpb3VzW24mMV07Cn0KCmludCBtYWluKCkgewoJaW50IG4gPSAxMDAwMDsKCUJpZ0ludCogYmlnaW50ID0gQmlnSW50OjpmaWJvbmFjY2kobik7Cgljb3V0IDw8ICpiaWdpbnQgPDwgZW5kbDsKCWRlbGV0ZSBiaWdpbnQ7CglyZXR1cm4gMDsKfQ==