fork download

copy

#include<iostream>
#include<string>
using namespace std;
template <class Blk>
class NumberlikeArray {
public:
    typedef unsigned int Index;
	static const unsigned int N;
	Index cap;
	Index len;
	Blk *blk;
	NumberlikeArray(Index c) : cap(c), len(0) { blk = (cap > 0) ? (new Blk[cap]) : NULL;}
	NumberlikeArray() : cap(0), len(0) {blk = NULL;}
	~NumberlikeArray() {delete [] blk;}
	void allocate(Index c);
	void allocateAndCopy(Index c);
	NumberlikeArray(const NumberlikeArray<Blk> &x);
	void operator=(const NumberlikeArray<Blk> &x);
	NumberlikeArray(const Blk *b, Index blen);
	Index getCapacity()     const { return cap; }
	Index getLength()       const { return len; }
	Blk   getBlock(Index i) const { return blk[i];   }
	bool  isEmpty()         const { return len == 0; }
	bool operator ==(const NumberlikeArray<Blk> &x) const;
	bool operator !=(const NumberlikeArray<Blk> &x) const {	return !operator ==(x);	}
};
template <class Blk>
const unsigned int NumberlikeArray<Blk>::N = 8 * sizeof(Blk);
template <class Blk>
void NumberlikeArray<Blk>::allocate(Index c) {if (c > cap) {delete [] blk;cap = c;blk = new Blk[cap];}}
template <class Blk>
void NumberlikeArray<Blk>::allocateAndCopy(Index c) {if (c > cap) {Blk *oldBlk = blk;cap = c;blk = new Blk[cap];Index i;
		for (i = 0; i < len; i++)
			blk[i] = oldBlk[i];
		delete [] oldBlk;
	}
}
template <class Blk>
NumberlikeArray<Blk>::NumberlikeArray(const NumberlikeArray<Blk> &x)
		: len(x.len) {
	cap = len;
	blk = new Blk[cap];
	Index i;
	for (i = 0; i < len; i++)
		blk[i] = x.blk[i];
}
template <class Blk>
void NumberlikeArray<Blk>::operator=(const NumberlikeArray<Blk> &x) {
	if (this == &x)
		return;
	len = x.len;
	allocate(len);
	Index i;
	for (i = 0; i < len; i++)
		blk[i] = x.blk[i];
}
template <class Blk>
NumberlikeArray<Blk>::NumberlikeArray(const Blk *b, Index blen)
		: cap(blen), len(blen) {
	blk = new Blk[cap];
	Index i;
	for (i = 0; i < len; i++)
		blk[i] = b[i];
}
template <class Blk>
bool NumberlikeArray<Blk>::operator ==(const NumberlikeArray<Blk> &x) const {
	if (len != x.len)
		return false;
	else {
		Index i;
		for (i = 0; i < len; i++)
			if (blk[i] != x.blk[i])
				return false;
		return true;
	}
}
class BigUnsigned : protected NumberlikeArray<unsigned long> {
public:
	enum CmpRes { less = -1, equal = 0, greater = 1 };
	typedef unsigned long Blk;
	typedef NumberlikeArray<Blk>::Index Index;
	NumberlikeArray<Blk>::N;
protected:
	BigUnsigned(int, Index c) : NumberlikeArray<Blk>(0, c) {}
	void zapLeadingZeros() { 
		while (len > 0 && blk[len - 1] == 0)
			len--;
	}
public:
	BigUnsigned() : NumberlikeArray<Blk>() {}
	BigUnsigned(const BigUnsigned &x) : NumberlikeArray<Blk>(x) {}
	void operator=(const BigUnsigned &x) {
		NumberlikeArray<Blk>::operator =(x);
	}
	BigUnsigned(const Blk *b, Index blen) : NumberlikeArray<Blk>(b, blen) {
		zapLeadingZeros();
	}
	~BigUnsigned() {}
	BigUnsigned(unsigned long  x);
	BigUnsigned(         long  x);
	BigUnsigned(unsigned int   x);
	BigUnsigned(         int   x);
	BigUnsigned(unsigned short x);
	BigUnsigned(         short x);
protected:
	template <class X> void initFromPrimitive      (X x);
	template <class X> void initFromSignedPrimitive(X x);
public:
	unsigned long  toUnsignedLong () const;
	long           toLong         () const;
	unsigned int   toUnsignedInt  () const;
	int            toInt          () const;
	unsigned short toUnsignedShort() const;
	short          toShort        () const;
protected:
	template <class X> X convertToSignedPrimitive() const;
	template <class X> X convertToPrimitive      () const;
public:
	NumberlikeArray<Blk>::getCapacity;
	NumberlikeArray<Blk>::getLength;
	Blk getBlock(Index i) const { return i >= len ? 0 : blk[i]; }
	void setBlock(Index i, Blk newBlock);
	bool isZero() const { return NumberlikeArray<Blk>::isEmpty(); }
	Index bitLength() const;
	bool getBit(Index bi) const {return (getBlock(bi / N) & (Blk(1) << (bi % N))) != 0;}
	void setBit(Index bi, bool newBit);
	CmpRes compareTo(const BigUnsigned &x) const;
	bool operator ==(const BigUnsigned &x) const {return NumberlikeArray<Blk>::operator ==(x);}
	bool operator !=(const BigUnsigned &x) const {return NumberlikeArray<Blk>::operator !=(x);}
	bool operator < (const BigUnsigned &x) const { return compareTo(x) == less   ; }
	bool operator <=(const BigUnsigned &x) const { return compareTo(x) != greater; }
	bool operator >=(const BigUnsigned &x) const { return compareTo(x) != less   ; }
	bool operator > (const BigUnsigned &x) const { return compareTo(x) == greater; }
	void add(const BigUnsigned &a, const BigUnsigned &b);
	void subtract(const BigUnsigned &a, const BigUnsigned &b);
	void multiply(const BigUnsigned &a, const BigUnsigned &b);
	void bitAnd(const BigUnsigned &a, const BigUnsigned &b);
	void bitOr(const BigUnsigned &a, const BigUnsigned &b);
	void bitXor(const BigUnsigned &a, const BigUnsigned &b);
	void bitShiftLeft(const BigUnsigned &a, int b);
	void bitShiftRight(const BigUnsigned &a, int b);
	void divideWithRemainder(const BigUnsigned &b, BigUnsigned &q);
	BigUnsigned operator +(const BigUnsigned &x) const;
	BigUnsigned operator -(const BigUnsigned &x) const;
	BigUnsigned operator *(const BigUnsigned &x) const;
	BigUnsigned operator /(const BigUnsigned &x) const;
	BigUnsigned operator %(const BigUnsigned &x) const;
	BigUnsigned operator &(const BigUnsigned &x) const;
	BigUnsigned operator |(const BigUnsigned &x) const;
	BigUnsigned operator ^(const BigUnsigned &x) const;
	BigUnsigned operator <<(int b) const;
	BigUnsigned operator >>(int b) const;
	void operator +=(const BigUnsigned &x);
	void operator -=(const BigUnsigned &x);
	void operator *=(const BigUnsigned &x);
	void operator /=(const BigUnsigned &x);
	void operator %=(const BigUnsigned &x);
	void operator &=(const BigUnsigned &x);
	void operator |=(const BigUnsigned &x);
	void operator ^=(const BigUnsigned &x);
	void operator <<=(int b);
	void operator >>=(int b);
	void operator ++(   );
	void operator ++(int);
	void operator --(   );
	void operator --(int);
	friend Blk getShiftedBlock(const BigUnsigned &num, Index x,unsigned int y);
	template <class X>
	friend X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a);
};
inline BigUnsigned BigUnsigned::operator +(const BigUnsigned &x) const {BigUnsigned ans;ans.add(*this, x);return ans;}
inline BigUnsigned BigUnsigned::operator -(const BigUnsigned &x) const {BigUnsigned ans;ans.subtract(*this, x);return ans;}
inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const {BigUnsigned ans;ans.multiply(*this, x);return ans;}
inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const {if (x.isZero()) throw "BigUnsigned::operator /: division by zero";
	BigUnsigned q, r;
	r = *this;
	r.divideWithRemainder(x, q);
	return q;
}
inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const {
	if (x.isZero()) throw "BigUnsigned::operator %: division by zero";
	BigUnsigned q, r;
	r = *this;
	r.divideWithRemainder(x, q);
	return r;
}
inline BigUnsigned BigUnsigned::operator &(const BigUnsigned &x) const {BigUnsigned ans;ans.bitAnd(*this, x);return ans;}
inline BigUnsigned BigUnsigned::operator |(const BigUnsigned &x) const {BigUnsigned ans;ans.bitOr(*this, x);return ans;}
inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const {BigUnsigned ans;ans.bitXor(*this, x);return ans;}
inline BigUnsigned BigUnsigned::operator <<(int b) const {BigUnsigned ans;ans.bitShiftLeft(*this, b);return ans;}
inline BigUnsigned BigUnsigned::operator >>(int b) const {BigUnsigned ans;ans.bitShiftRight(*this, b);return ans;}
inline void BigUnsigned::operator +=(const BigUnsigned &x) {add(*this, x);}
inline void BigUnsigned::operator -=(const BigUnsigned &x) {subtract(*this, x);}
inline void BigUnsigned::operator *=(const BigUnsigned &x) {multiply(*this, x);}
inline void BigUnsigned::operator /=(const BigUnsigned &x) {if (x.isZero()) throw "BigUnsigned::operator /=: division by zero";
	BigUnsigned q;
	divideWithRemainder(x, q);
	*this = q;
}
inline void BigUnsigned::operator %=(const BigUnsigned &x) {if (x.isZero()) throw "BigUnsigned::operator %=: division by zero";
	BigUnsigned q;
	divideWithRemainder(x, q);
}
inline void BigUnsigned::operator &=(const BigUnsigned &x) {bitAnd(*this, x);}
inline void BigUnsigned::operator |=(const BigUnsigned &x) {bitOr(*this, x);}
inline void BigUnsigned::operator ^=(const BigUnsigned &x) {bitXor(*this, x);}
inline void BigUnsigned::operator <<=(int b) {bitShiftLeft(*this, b);}
inline void BigUnsigned::operator >>=(int b) {bitShiftRight(*this, b);}
template <class X>
void BigUnsigned::initFromPrimitive(X x) {
	if (x == 0)
		;
	else {
		cap = 1;
		blk = new Blk[1];
		len = 1;
		blk[0] = Blk(x);
	}
}
template <class X>
void BigUnsigned::initFromSignedPrimitive(X x) {
	if (x < 0)
		throw "BigUnsigned constructor: "
			"Cannot construct a BigUnsigned from a negative number";
	else
		initFromPrimitive(x);
}
template <class X>
X BigUnsigned::convertToPrimitive() const {
	if (len == 0)
		return 0;
	else if (len == 1) {
		X x = X(blk[0]);
		if (Blk(x) == blk[0])
			return x;
	}
	throw "BigUnsigned::to<Primitive>: "
		"Value is too big to fit in the requested type";
}
template <class X>
X BigUnsigned::convertToSignedPrimitive() const {
	X x = convertToPrimitive<X>();
	if (x >= 0)
		return x;
	else
		throw "BigUnsigned::to(Primitive): "
			"Value is too big to fit in the requested type";
}
class BigInteger {
public:
	typedef BigUnsigned::Blk Blk;
	typedef BigUnsigned::Index Index;
	typedef BigUnsigned::CmpRes CmpRes;
	static const CmpRes
		less    = BigUnsigned::less   ,
		equal   = BigUnsigned::equal  ,
		greater = BigUnsigned::greater;
	enum Sign { negative = -1, zero = 0, positive = 1 };
 
protected:
	Sign sign;
	BigUnsigned mag;
 
public:
	BigInteger() : sign(zero), mag() {}
	BigInteger(const BigInteger &x) : sign(x.sign), mag(x.mag) {};
	void operator=(const BigInteger &x);
	BigInteger(const Blk *b, Index blen, Sign s);
	BigInteger(const Blk *b, Index blen) : mag(b, blen) {
		sign = mag.isZero() ? zero : positive;
	}
	BigInteger(const BigUnsigned &x, Sign s);
	BigInteger(const BigUnsigned &x) : mag(x) {
		sign = mag.isZero() ? zero : positive;
	}
	BigInteger(unsigned long  x);
	BigInteger(         long  x);
	BigInteger(unsigned int   x);
	BigInteger(         int   x);
	BigInteger(unsigned short x);
	BigInteger(         short x);
	unsigned long  toUnsignedLong () const;
	long           toLong         () const;
	unsigned int   toUnsignedInt  () const;
	int            toInt          () const;
	unsigned short toUnsignedShort() const;
	short          toShort        () const;
protected:
	template <class X> X convertToUnsignedPrimitive() const;
	template <class X, class UX> X convertToSignedPrimitive() const;
public:
	Sign getSign() const { return sign; }
	const BigUnsigned &getMagnitude() const { return mag; }
	Index getLength() const { return mag.getLength(); }
	Index getCapacity() const { return mag.getCapacity(); }
	Blk getBlock(Index i) const { return mag.getBlock(i); }
	bool isZero() const { return sign == zero; }
	CmpRes compareTo(const BigInteger &x) const;
	bool operator ==(const BigInteger &x) const {
		return sign == x.sign && mag == x.mag;
	}
	bool operator !=(const BigInteger &x) const { return !operator ==(x); };
	bool operator < (const BigInteger &x) const { return compareTo(x) == less   ; }
	bool operator <=(const BigInteger &x) const { return compareTo(x) != greater; }
	bool operator >=(const BigInteger &x) const { return compareTo(x) != less   ; }
	bool operator > (const BigInteger &x) const { return compareTo(x) == greater; }
	void add     (const BigInteger &a, const BigInteger &b);
	void subtract(const BigInteger &a, const BigInteger &b);
	void multiply(const BigInteger &a, const BigInteger &b);
	void divideWithRemainder(const BigInteger &b, BigInteger &q);
	void negate(const BigInteger &a);
	BigInteger operator +(const BigInteger &x) const;
	BigInteger operator -(const BigInteger &x) const;
	BigInteger operator *(const BigInteger &x) const;
	BigInteger operator /(const BigInteger &x) const;
	BigInteger operator %(const BigInteger &x) const;
	BigInteger operator -() const;
	void operator +=(const BigInteger &x);
	void operator -=(const BigInteger &x);
	void operator *=(const BigInteger &x);
	void operator /=(const BigInteger &x);
	void operator %=(const BigInteger &x);
	void flipSign();
	void operator ++(   );
	void operator ++(int);
	void operator --(   );
	void operator --(int);
};
inline BigInteger BigInteger::operator +(const BigInteger &x) const {
	BigInteger ans;
	ans.add(*this, x);
	return ans;
}
inline BigInteger BigInteger::operator -(const BigInteger &x) const {
	BigInteger ans;
	ans.subtract(*this, x);
	return ans;
}
inline BigInteger BigInteger::operator *(const BigInteger &x) const {
	BigInteger ans;
	ans.multiply(*this, x);
	return ans;
}
inline BigInteger BigInteger::operator /(const BigInteger &x) const {
	if (x.isZero()) throw "BigInteger::operator /: division by zero";
	BigInteger q, r;
	r = *this;
	r.divideWithRemainder(x, q);
	return q;
}
inline BigInteger BigInteger::operator %(const BigInteger &x) const {
	if (x.isZero()) throw "BigInteger::operator %: division by zero";
	BigInteger q, r;
	r = *this;
	r.divideWithRemainder(x, q);
	return r;
}
inline BigInteger BigInteger::operator -() const {
	BigInteger ans;
	ans.negate(*this);
	return ans;
}
inline void BigInteger::operator +=(const BigInteger &x) {
	add(*this, x);
}
inline void BigInteger::operator -=(const BigInteger &x) {
	subtract(*this, x);
}
inline void BigInteger::operator *=(const BigInteger &x) {
	multiply(*this, x);
}
inline void BigInteger::operator /=(const BigInteger &x) {
	if (x.isZero()) throw "BigInteger::operator /=: division by zero";
	BigInteger q;
	divideWithRemainder(x, q);
	*this = q;
}
inline void BigInteger::operator %=(const BigInteger &x) {
	if (x.isZero()) throw "BigInteger::operator %=: division by zero";
	BigInteger q;
	divideWithRemainder(x, q);
}
inline void BigInteger::flipSign() {
	sign = Sign(-sign);
}
BigUnsigned gcd(BigUnsigned a, BigUnsigned b);
void extendedEuclidean(BigInteger m, BigInteger n,
		BigInteger &g, BigInteger &r, BigInteger &s);
BigUnsigned modinv(const BigInteger &x, const BigUnsigned &n);
BigUnsigned modexp(const BigInteger &base, const BigUnsigned &exponent,
		const BigUnsigned &modulus);
class BigUnsignedInABase : protected NumberlikeArray<unsigned short> {
public:
	typedef unsigned short Digit;
	typedef Digit Base;
protected:
	Base base;
	BigUnsignedInABase(int, Index c) : NumberlikeArray<Digit>(0, c) {}
	void zapLeadingZeros() { 
		while (len > 0 && blk[len - 1] == 0)
			len--;
	}
public:
	BigUnsignedInABase() : NumberlikeArray<Digit>(), base(2) {}
	BigUnsignedInABase(const BigUnsignedInABase &x) : NumberlikeArray<Digit>(x), base(x.base) {}
	void operator =(const BigUnsignedInABase &x) {
		NumberlikeArray<Digit>::operator =(x);
		base = x.base;
	}
	BigUnsignedInABase(const Digit *d, Index l, Base base);
	~BigUnsignedInABase() {}
	BigUnsignedInABase(const BigUnsigned &x, Base base);
	operator BigUnsigned() const;
	operator std::string() const;
	BigUnsignedInABase(const std::string &s, Base base);
 
public:
	Base getBase() const { return base; }
	NumberlikeArray<Digit>::getCapacity;
	NumberlikeArray<Digit>::getLength;
	Digit getDigit(Index i) const { return i >= len ? 0 : blk[i]; }
	bool isZero() const { return NumberlikeArray<Digit>::isEmpty(); }
	bool operator ==(const BigUnsignedInABase &x) const {
		return base == x.base && NumberlikeArray<Digit>::operator ==(x);
	}
	bool operator !=(const BigUnsignedInABase &x) const { return !operator ==(x); }
};
std::string bigUnsignedToString(const BigUnsigned &x);
std::string bigIntegerToString(const BigInteger &x);
BigUnsigned stringToBigUnsigned(const std::string &s);
BigInteger stringToBigInteger(const std::string &s);
template <class T>
BigInteger dataToBigInteger(const T* data, BigInteger::Index length, BigInteger::Sign sign);
std::ostream &operator <<(std::ostream &os, const BigUnsigned &x);
std::ostream &operator <<(std::ostream &os, const BigInteger &x);
template <class T>
BigInteger dataToBigInteger(const T* data, BigInteger::Index length, BigInteger::Sign sign) {
	unsigned int pieceSizeInBits = 8 * sizeof(T);
	unsigned int piecesPerBlock = sizeof(BigInteger::Blk) / sizeof(T);
	unsigned int numBlocks = (length + piecesPerBlock - 1) / piecesPerBlock;
	BigInteger::Blk *blocks = new BigInteger::Blk[numBlocks];
	BigInteger::Index blockNum, pieceNum, pieceNumHere;
	for (blockNum = 0, pieceNum = 0; blockNum < numBlocks; blockNum++) {
		BigInteger::Blk curBlock = 0;
		for (pieceNumHere = 0; pieceNumHere < piecesPerBlock && pieceNum < length;
			pieceNumHere++, pieceNum++)
			curBlock |= (BigInteger::Blk(data[pieceNum]) << (pieceSizeInBits * pieceNumHere));
		blocks[blockNum] = curBlock;
	}
	BigInteger x(blocks, numBlocks, sign);
	delete [] blocks;
	return x;
}
BigUnsigned::BigUnsigned(unsigned long  x) { initFromPrimitive      (x); }
BigUnsigned::BigUnsigned(unsigned int   x) { initFromPrimitive      (x); }
BigUnsigned::BigUnsigned(unsigned short x) { initFromPrimitive      (x); }
BigUnsigned::BigUnsigned(         long  x) { initFromSignedPrimitive(x); }
BigUnsigned::BigUnsigned(         int   x) { initFromSignedPrimitive(x); }
BigUnsigned::BigUnsigned(         short x) { initFromSignedPrimitive(x); }
unsigned long  BigUnsigned::toUnsignedLong () const { return convertToPrimitive      <unsigned long >(); }
unsigned int   BigUnsigned::toUnsignedInt  () const { return convertToPrimitive      <unsigned int  >(); }
unsigned short BigUnsigned::toUnsignedShort() const { return convertToPrimitive      <unsigned short>(); }
long           BigUnsigned::toLong         () const { return convertToSignedPrimitive<         long >(); }
int            BigUnsigned::toInt          () const { return convertToSignedPrimitive<         int  >(); }
short          BigUnsigned::toShort        () const { return convertToSignedPrimitive<         short>(); }
void BigUnsigned::setBlock(Index i, Blk newBlock) {
	if (newBlock == 0) {
		if (i < len) {
			blk[i] = 0;
			zapLeadingZeros();
		}
	} else {
		if (i >= len) {
			allocateAndCopy(i+1);
			for (Index j = len; j < i; j++)
				blk[j] = 0;
			len = i+1;
		}
		blk[i] = newBlock;
	}
}
BigUnsigned::Index BigUnsigned::bitLength() const {
	if (isZero())
		return 0;
	else {
		Blk leftmostBlock = getBlock(len - 1);
		Index leftmostBlockLen = 0;
		while (leftmostBlock != 0) {
			leftmostBlock >>= 1;
			leftmostBlockLen++;
		}
		return leftmostBlockLen + (len - 1) * N;
	}
}
void BigUnsigned::setBit(Index bi, bool newBit) {
	Index blockI = bi / N;
	Blk block = getBlock(blockI), mask = Blk(1) << (bi % N);
	block = newBit ? (block | mask) : (block & ~mask);
	setBlock(blockI, block);
}
BigUnsigned::CmpRes BigUnsigned::compareTo(const BigUnsigned &x) const {
	if (len < x.len)
		return less;
	else if (len > x.len)
		return greater;
	else {
		Index i = len;
		while (i > 0) {
			i--;
			if (blk[i] == x.blk[i])
				continue;
			else if (blk[i] > x.blk[i])
				return greater;
			else
				return less;
		}
		return equal;
	}
}
#define DTRT_ALIASED(cond, op) \
	if (cond) { \
		BigUnsigned tmpThis; \
		tmpThis.op; \
		*this = tmpThis; \
		return; \
	}
void BigUnsigned::add(const BigUnsigned &a, const BigUnsigned &b) {
	DTRT_ALIASED(this == &a || this == &b, add(a, b));
	if (a.len == 0) {
		operator =(b);
		return;
	} else if (b.len == 0) {
		operator =(a);
		return;
	}
	bool carryIn, carryOut;
	Blk temp;
	Index i;
	const BigUnsigned *a2, *b2;
	if (a.len >= b.len) {
		a2 = &a;
		b2 = &b;
	} else {
		a2 = &b;
		b2 = &a;
	}
	len = a2->len + 1;
	allocate(len);
	for (i = 0, carryIn = false; i < b2->len; i++) {
		temp = a2->blk[i] + b2->blk[i];
		carryOut = (temp < a2->blk[i]);
		if (carryIn) {
			temp++;
			carryOut |= (temp == 0);
		}
		blk[i] = temp;
		carryIn = carryOut;
	}
	for (; i < a2->len && carryIn; i++) {
		temp = a2->blk[i] + 1;
		carryIn = (temp == 0);
		blk[i] = temp;
	}
	for (; i < a2->len; i++)
		blk[i] = a2->blk[i];
	if (carryIn)
		blk[i] = 1;
	else
		len--;
}
void BigUnsigned::subtract(const BigUnsigned &a, const BigUnsigned &b) {
	DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
	if (b.len == 0) {
		operator =(a);
		return;
	} else if (a.len < b.len)
		throw "BigUnsigned::subtract: "
			"Negative result in unsigned calculation";
	bool borrowIn, borrowOut;
	Blk temp;
	Index i;
	len = a.len;
	allocate(len);
	for (i = 0, borrowIn = false; i < b.len; i++) {
		temp = a.blk[i] - b.blk[i];
		borrowOut = (temp > a.blk[i]);
		if (borrowIn) {
			borrowOut |= (temp == 0);
			temp--;
		}
		blk[i] = temp;
		borrowIn = borrowOut;
	}
	for (; i < a.len && borrowIn; i++) {
		borrowIn = (a.blk[i] == 0);
		blk[i] = a.blk[i] - 1;
	}
	if (borrowIn) {
		len = 0;
		throw "BigUnsigned::subtract: Negative result in unsigned calculation";
	} 
	else
		for (; i < a.len; i++)
			blk[i] = a.blk[i];
	zapLeadingZeros();
}
inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num,
	BigUnsigned::Index x, unsigned int y) {
	BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y));
	BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y);
	return part1 | part2;
}
void BigUnsigned::multiply(const BigUnsigned &a, const BigUnsigned &b) {
	DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
	if (a.len == 0 || b.len == 0) {
		len = 0;
		return;
	}
	Index i, j, k;
	unsigned int i2;
	Blk temp;
	bool carryIn, carryOut;
	len = a.len + b.len;
	allocate(len);
	for (i = 0; i < len; i++)
		blk[i] = 0;
	for (i = 0; i < a.len; i++) {
		for (i2 = 0; i2 < N; i2++) {
			if ((a.blk[i] & (Blk(1) << i2)) == 0)
				continue;
			for (j = 0, k = i, carryIn = false; j <= b.len; j++, k++) {
				temp = blk[k] + getShiftedBlock(b, j, i2);
				carryOut = (temp < blk[k]);
				if (carryIn) {
					temp++;
					carryOut |= (temp == 0);
				}
				blk[k] = temp;
				carryIn = carryOut;
			}
			for (; carryIn; k++) {
				blk[k]++;
				carryIn = (blk[k] == 0);
			}
		}
	}
	if (blk[len - 1] == 0)
		len--;
}
void BigUnsigned::divideWithRemainder(const BigUnsigned &b, BigUnsigned &q) {
	if (this == &q)
		throw "BigUnsigned::divideWithRemainder: Cannot write quotient and remainder into the same variable";
	if (this == &b || &q == &b) {
		BigUnsigned tmpB(b);
		divideWithRemainder(tmpB, q);
		return;
	}
	if (b.len == 0) {
		q.len = 0;
		return;
	}
	if (len < b.len) {
		q.len = 0;
		return;
	}
	Index i, j, k;
	unsigned int i2;
	Blk temp;
	bool borrowIn, borrowOut;
	Index origLen = len;
	allocateAndCopy(len + 1);
	len++;
	blk[origLen] = 0;
	Blk *subtractBuf = new Blk[len];
	q.len = origLen - b.len + 1;
	q.allocate(q.len);
	for (i = 0; i < q.len; i++)
		q.blk[i] = 0;
	i = q.len;
	while (i > 0) {
		i--;
		q.blk[i] = 0;
		i2 = N;
		while (i2 > 0) {
			i2--;
			for (j = 0, k = i, borrowIn = false; j <= b.len; j++, k++) {
				temp = blk[k] - getShiftedBlock(b, j, i2);
				borrowOut = (temp > blk[k]);
				if (borrowIn) {
					borrowOut |= (temp == 0);
					temp--;
				}
				subtractBuf[k] = temp; 
				borrowIn = borrowOut;
			}
			for (; k < origLen && borrowIn; k++) {
				borrowIn = (blk[k] == 0);
				subtractBuf[k] = blk[k] - 1;
			}
			if (!borrowIn) {
				q.blk[i] |= (Blk(1) << i2);
				while (k > i) {
					k--;
					blk[k] = subtractBuf[k];
				}
			} 
		}
	}
	if (q.blk[q.len - 1] == 0)
		q.len--;
	zapLeadingZeros();
	delete [] subtractBuf;
}
void BigUnsigned::bitAnd(const BigUnsigned &a, const BigUnsigned &b) {
	DTRT_ALIASED(this == &a || this == &b, bitAnd(a, b));
	len = (a.len >= b.len) ? b.len : a.len;
	allocate(len);
	Index i;
	for (i = 0; i < len; i++)
		blk[i] = a.blk[i] & b.blk[i];
	zapLeadingZeros();
}
void BigUnsigned::bitOr(const BigUnsigned &a, const BigUnsigned &b) {
	DTRT_ALIASED(this == &a || this == &b, bitOr(a, b));
	Index i;
	const BigUnsigned *a2, *b2;
	if (a.len >= b.len) {
		a2 = &a;
		b2 = &b;
	} else {
		a2 = &b;
		b2 = &a;
	}
	allocate(a2->len);
	for (i = 0; i < b2->len; i++)
		blk[i] = a2->blk[i] | b2->blk[i];
	for (; i < a2->len; i++)
		blk[i] = a2->blk[i];
	len = a2->len;
}
void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) {
	DTRT_ALIASED(this == &a || this == &b, bitXor(a, b));
	Index i;
	const BigUnsigned *a2, *b2;
	if (a.len >= b.len) {
		a2 = &a;
		b2 = &b;
	} else {
		a2 = &b;
		b2 = &a;
	}
	allocate(a2->len);
	for (i = 0; i < b2->len; i++)
		blk[i] = a2->blk[i] ^ b2->blk[i];
	for (; i < a2->len; i++)
		blk[i] = a2->blk[i];
	len = a2->len;
	zapLeadingZeros();
}
void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) {
	DTRT_ALIASED(this == &a, bitShiftLeft(a, b));
	if (b < 0) {
		if (b << 1 == 0)
			throw "BigUnsigned::bitShiftLeft: "
				"Pathological shift amount not implemented";
		else {
			bitShiftRight(a, -b);
			return;
		}
	}
	Index shiftBlocks = b / N;
	unsigned int shiftBits = b % N;
	len = a.len + shiftBlocks + 1;
	allocate(len);
	Index i, j;
	for (i = 0; i < shiftBlocks; i++)
		blk[i] = 0;
	for (j = 0, i = shiftBlocks; j <= a.len; j++, i++)
		blk[i] = getShiftedBlock(a, j, shiftBits);
	if (blk[len - 1] == 0)
		len--;
}
void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) {
	DTRT_ALIASED(this == &a, bitShiftRight(a, b));
	if (b < 0) {
		if (b << 1 == 0)
			throw "BigUnsigned::bitShiftRight: "
				"Pathological shift amount not implemented";
		else {
			bitShiftLeft(a, -b);
			return;
		}
	}
	Index rightShiftBlocks = (b + N - 1) / N;
	unsigned int leftShiftBits = N * rightShiftBlocks - b;
	if (rightShiftBlocks >= a.len + 1) {
		len = 0;
		return;
	}
	len = a.len + 1 - rightShiftBlocks;
	allocate(len);
	Index i, j;
	for (j = rightShiftBlocks, i = 0; j <= a.len; j++, i++)
		blk[i] = getShiftedBlock(a, j, leftShiftBits);
	if (blk[len - 1] == 0)
		len--;
}
void BigUnsigned::operator ++() {
	Index i;
	bool carry = true;
	for (i = 0; i < len && carry; i++) {
		blk[i]++;
		carry = (blk[i] == 0);
	}
	if (carry) {
		allocateAndCopy(len + 1);
		len++;
		blk[i] = 1;
	}
}
void BigUnsigned::operator ++(int) {
	operator ++();
}
void BigUnsigned::operator --() {
	if (len == 0)
		throw "BigUnsigned::operator --(): Cannot decrement an unsigned zero";
	Index i;
	bool borrow = true;
	for (i = 0; borrow; i++) {
		borrow = (blk[i] == 0);
		blk[i]--;
	}
	if (blk[len - 1] == 0)
		len--;
}
void BigUnsigned::operator --(int) {
	operator --();
}
void BigInteger::operator =(const BigInteger &x) {
	if (this == &x)
		return;
	sign = x.sign;
	mag = x.mag;
}
BigInteger::BigInteger(const Blk *b, Index blen, Sign s) : mag(b, blen) {
	switch (s) {
	case zero:
		if (!mag.isZero())
			throw "BigInteger::BigInteger(const Blk *, Index, Sign): Cannot use a sign of zero with a nonzero magnitude";
		sign = zero;
		break;
	case positive:
	case negative:
		sign = mag.isZero() ? zero : s;
		break;
	default:
		throw "BigInteger::BigInteger(const Blk *, Index, Sign): Invalid sign";
	}
}
BigInteger::BigInteger(const BigUnsigned &x, Sign s) : mag(x) {
	switch (s) {
	case zero:
		if (!mag.isZero())
			throw "BigInteger::BigInteger(const BigUnsigned &, Sign): Cannot use a sign of zero with a nonzero magnitude";
		sign = zero;
		break;
	case positive:
	case negative:
		sign = mag.isZero() ? zero : s;
		break;
	default:
		throw "BigInteger::BigInteger(const BigUnsigned &, Sign): Invalid sign";
	}
}
BigInteger::BigInteger(unsigned long  x) : mag(x) { sign = mag.isZero() ? zero : positive; }
BigInteger::BigInteger(unsigned int   x) : mag(x) { sign = mag.isZero() ? zero : positive; }
BigInteger::BigInteger(unsigned short x) : mag(x) { sign = mag.isZero() ? zero : positive; }
namespace {
	template <class X, class UX>
	BigInteger::Blk magOf(X x) {
		return BigInteger::Blk(x < 0 ? UX(-x) : x);
	}
	template <class X>
	BigInteger::Sign signOf(X x) {
		return (x == 0) ? BigInteger::zero
			: (x > 0) ? BigInteger::positive
			: BigInteger::negative;
	}
}
BigInteger::BigInteger(long  x) : sign(signOf(x)), mag(magOf<long , unsigned long >(x)) {}
BigInteger::BigInteger(int   x) : sign(signOf(x)), mag(magOf<int  , unsigned int  >(x)) {}
BigInteger::BigInteger(short x) : sign(signOf(x)), mag(magOf<short, unsigned short>(x)) {}
template <class X>
inline X convertBigUnsignedToPrimitiveAccess(const BigUnsigned &a) {
	return a.convertToPrimitive<X>();
}
template <class X>
X BigInteger::convertToUnsignedPrimitive() const {
	if (sign == negative)
		throw "BigInteger::to<Primitive>: "
			"Cannot convert a negative integer to an unsigned type";
	else
		return convertBigUnsignedToPrimitiveAccess<X>(mag);
}
template <class X, class UX>
X BigInteger::convertToSignedPrimitive() const {
	if (sign == zero)
		return 0;
	else if (mag.getLength() == 1) {Blk b = mag.getBlock(0);if (sign == positive) {	X x = X(b);	if (x >= 0 && Blk(x) == b)	return x;} 
	else {X x = -X(b);if (x < 0 && Blk(UX(-x)) == b)return x;}
	}
	throw "BigInteger::to<Primitive>: "
		"Value is too big to fit in the requested type";
}
unsigned long  BigInteger::toUnsignedLong () const { return convertToUnsignedPrimitive<unsigned long >       (); }
unsigned int   BigInteger::toUnsignedInt  () const { return convertToUnsignedPrimitive<unsigned int  >       (); }
unsigned short BigInteger::toUnsignedShort() const { return convertToUnsignedPrimitive<unsigned short>       (); }
long           BigInteger::toLong         () const { return convertToSignedPrimitive  <long , unsigned long> (); }
int            BigInteger::toInt          () const { return convertToSignedPrimitive  <int  , unsigned int>  (); }
short          BigInteger::toShort        () const { return convertToSignedPrimitive  <short, unsigned short>(); }
BigInteger::CmpRes BigInteger::compareTo(const BigInteger &x) const {
	if (sign < x.sign)
		return less;
	else if (sign > x.sign)
		return greater;
	else switch (sign) {
	case zero:
		return equal;
	case positive:
		return mag.compareTo(x.mag);
	case negative:
		return CmpRes(-mag.compareTo(x.mag));
	default:
		throw "BigInteger internal error";
	}
}
#define DTRT_ALIASED(cond, op) \
	if (cond) { \
		BigInteger tmpThis; \
		tmpThis.op; \
		*this = tmpThis; \
		return; \
	}
void BigInteger::add(const BigInteger &a, const BigInteger &b) {
	DTRT_ALIASED(this == &a || this == &b, add(a, b));
	if (a.sign == zero)
		operator =(b);
	else if (b.sign == zero)
		operator =(a);
	else if (a.sign == b.sign) {sign = a.sign;	mag.add(a.mag, b.mag);} 
	else {	switch (a.mag.compareTo(b.mag)) {
		case equal:
			mag = 0;
			sign = zero;
			break;
		case greater:
			sign = a.sign;
			mag.subtract(a.mag, b.mag);
			break;
		case less:
			sign = b.sign;
			mag.subtract(b.mag, a.mag);
			break;
		}
	}
}
void BigInteger::subtract(const BigInteger &a, const BigInteger &b) {
	DTRT_ALIASED(this == &a || this == &b, subtract(a, b));
	if (a.sign == zero) {
		mag = b.mag;
		sign = Sign(-b.sign);
	} else if (b.sign == zero)
		operator =(a);
	else if (a.sign != b.sign) {	sign = a.sign;	mag.add(a.mag, b.mag);	} 
	else {	switch (a.mag.compareTo(b.mag)) {	case equal:		mag = 0;	sign = zero; break;
		case greater:
			sign = a.sign;
			mag.subtract(a.mag, b.mag);
			break;
		case less:
			sign = Sign(-b.sign);
			mag.subtract(b.mag, a.mag);
			break;
		}
	}
}
void BigInteger::multiply(const BigInteger &a, const BigInteger &b) {
	DTRT_ALIASED(this == &a || this == &b, multiply(a, b));
	if (a.sign == zero || b.sign == zero) {		sign = zero;		mag = 0;		return;	}
	sign = (a.sign == b.sign) ? positive : negative;
	mag.multiply(a.mag, b.mag);
}
 
void BigInteger::divideWithRemainder(const BigInteger &b, BigInteger &q) {
	if (this == &q)
		throw "BigInteger::divideWithRemainder: Cannot write quotient and remainder into the same variable";
	if (this == &b || &q == &b) {
		BigInteger tmpB(b);
		divideWithRemainder(tmpB, q);
		return;
	}
	if (b.sign == zero) {		q.mag = 0;		q.sign = zero;		return;	}
	if (sign == zero) {		q.mag = 0;		q.sign = zero;		return;	}
	if (sign == b.sign) {		q.sign = positive;	} 
	else {	q.sign = negative;	mag--;}
	mag.divideWithRemainder(b.mag, q.mag);
	if (sign != b.sign) {
		q.mag++;
		mag.subtract(b.mag, mag);
		mag--;
	}
	sign = b.sign;
	if (mag.isZero())	sign = zero;
	if (q.mag.isZero())	q.sign = zero;
}
void BigInteger::negate(const BigInteger &a) {
	DTRT_ALIASED(this == &a, negate(a));
	mag = a.mag;
	sign = Sign(-a.sign);
}
void BigInteger::operator ++() {
	if (sign == negative) {
		mag--;
		if (mag == 0)
			sign = zero;
	} else {
		mag++;
		sign = positive;
	}
}
void BigInteger::operator ++(int) {
	operator ++();
}
void BigInteger::operator --() {
	if (sign == positive) {
		mag--;
		if (mag == 0)
			sign = zero;
	} else {
		mag++;
		sign = negative;
	}
}
void BigInteger::operator --(int) {
	operator --();
}
BigUnsigned gcd(BigUnsigned a, BigUnsigned b) {
	BigUnsigned trash;
	for (;;) {
		if (b.isZero())
			return a;
		a.divideWithRemainder(b, trash);
		if (a.isZero())
			return b;
		b.divideWithRemainder(a, trash);
	}
}
void extendedEuclidean(BigInteger m, BigInteger n,
		BigInteger &g, BigInteger &r, BigInteger &s) {
	if (&g == &r || &g == &s || &r == &s)
		throw "BigInteger extendedEuclidean: Outputs are aliased";
	BigInteger r1(1), s1(0), r2(0), s2(1), q;
	for (;;) {
		if (n.isZero()) {
			r = r1; s = s1; g = m;
			return;
		}
		m.divideWithRemainder(n, q);
		r1 -= q*r2; s1 -= q*s2;
 
		if (m.isZero()) {
			r = r2; s = s2; g = n;
			return;
		}
		n.divideWithRemainder(m, q);
		r2 -= q*r1; s2 -= q*s1;
	}
}
BigUnsigned modinv(const BigInteger &x, const BigUnsigned &n) {
	BigInteger g, r, s;
	extendedEuclidean(x, n, g, r, s);
	if (g == 1)
		return (r % n).getMagnitude();
	else
		throw "BigInteger modinv: x and n have a common factor";
}
BigUnsigned modexp(const BigInteger &base, const BigUnsigned &exponent,
		const BigUnsigned &modulus) {
	BigUnsigned ans = 1, base2 = (base % modulus).getMagnitude();
	BigUnsigned::Index i = exponent.bitLength();
	while (i > 0) {
		i--;
		ans *= ans;
		ans %= modulus;
		if (exponent.getBit(i)) {
			ans *= base2;
			ans %= modulus;
		}
	}
	return ans;
}
BigUnsignedInABase::BigUnsignedInABase(const Digit *d, Index l, Base base)
	: NumberlikeArray<Digit>(d, l), base(base) {
	if (base < 2)
		throw "BigUnsignedInABase::BigUnsignedInABase(const Digit *, Index, Base): The base must be at least 2";
	for (Index i = 0; i < l; i++)
		if (blk[i] >= base)
			throw "BigUnsignedInABase::BigUnsignedInABase(const Digit *, Index, Base): A digit is too large for the specified base";
	zapLeadingZeros();
}
namespace {
	unsigned int bitLen(unsigned int x) {
		unsigned int len = 0;
		while (x > 0) {
			x >>= 1;
			len++;
		}
		return len;
	}
	unsigned int ceilingDiv(unsigned int a, unsigned int b) {
		return (a + b - 1) / b;
	}
}
BigUnsignedInABase::BigUnsignedInABase(const BigUnsigned &x, Base base) {
	if (base < 2)
		throw "BigUnsignedInABase(BigUnsigned, Base): The base must be at least 2";
	this->base = base;
	int maxBitLenOfX = x.getLength() * BigUnsigned::N;
	int minBitsPerDigit = bitLen(base) - 1;
	int maxDigitLenOfX = ceilingDiv(maxBitLenOfX, minBitsPerDigit);
	len = maxDigitLenOfX;
	allocate(len);
	BigUnsigned x2(x), buBase(base);
	Index digitNum = 0;
	while (!x2.isZero()) {
		BigUnsigned lastDigit(x2);
		lastDigit.divideWithRemainder(buBase, x2);
		blk[digitNum] = lastDigit.toUnsignedShort();
		digitNum++;
	}
	len = digitNum;
}
BigUnsignedInABase::operator BigUnsigned() const {
	BigUnsigned ans(0), buBase(base), temp;
	Index digitNum = len;
	while (digitNum > 0) {
		digitNum--;
		temp.multiply(ans, buBase);
		ans.add(temp, BigUnsigned(blk[digitNum]));
	}
	return ans;
}
BigUnsignedInABase::BigUnsignedInABase(const std::string &s, Base base) {
	if (base > 36)
		throw "BigUnsignedInABase(std::string, Base): The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36.  You tried a conversion with a base over 36; write your own string conversion routine.";
	this->base = base;
	len = Index(s.length());
	allocate(len);
	Index digitNum, symbolNumInString;
	for (digitNum = 0; digitNum < len; digitNum++) {
		symbolNumInString = len - 1 - digitNum;
		char theSymbol = s[symbolNumInString];
		if (theSymbol >= '0' && theSymbol <= '9')
			blk[digitNum] = theSymbol - '0';
		else if (theSymbol >= 'A' && theSymbol <= 'Z')
			blk[digitNum] = theSymbol - 'A' + 10;
		else if (theSymbol >= 'a' && theSymbol <= 'z')
			blk[digitNum] = theSymbol - 'a' + 10;
		else
			throw "BigUnsignedInABase(std::string, Base): Bad symbol in input.  Only 0-9, A-Z, a-z are accepted.";
		if (blk[digitNum] >= base)
			throw "BigUnsignedInABase::BigUnsignedInABase(const Digit *, Index, Base): A digit is too large for the specified base";
	}
	zapLeadingZeros();
}
BigUnsignedInABase::operator std::string() const {
	if (base > 36)
		throw "BigUnsignedInABase ==> std::string: The default string conversion routines use the symbol set 0-9, A-Z and therefore support only up to base 36.  You tried a conversion with a base over 36; write your own string conversion routine.";
	if (len == 0)
		return std::string("0");
	char *s = new char[len + 1];
	s[len] = '\0';
	Index digitNum, symbolNumInString;
	for (symbolNumInString = 0; symbolNumInString < len; symbolNumInString++) {
		digitNum = len - 1 - symbolNumInString;
		Digit theDigit = blk[digitNum];
		if (theDigit < 10)
			s[symbolNumInString] = char('0' + theDigit);
		else
			s[symbolNumInString] = char('A' + theDigit - 10);
	}
	std::string s2(s);
	delete [] s;
	return s2;
}
std::string bigUnsignedToString(const BigUnsigned &x) {
	return std::string(BigUnsignedInABase(x, 10));
}
std::string bigIntegerToString(const BigInteger &x) {
	return (x.getSign() == BigInteger::negative)
		? (std::string("-") + bigUnsignedToString(x.getMagnitude()))
		: (bigUnsignedToString(x.getMagnitude()));
}
BigUnsigned stringToBigUnsigned(const std::string &s) {
	return BigUnsigned(BigUnsignedInABase(s, 10));
}
BigInteger stringToBigInteger(const std::string &s) {
	return (s[0] == '-') ? BigInteger(stringToBigUnsigned(s.substr(1, s.length() - 1)), BigInteger::negative)
		: (s[0] == '+') ? BigInteger(stringToBigUnsigned(s.substr(1, s.length() - 1)))
		: BigInteger(stringToBigUnsigned(s));
}
std::ostream &operator <<(std::ostream &os, const BigUnsigned &x) {
	BigUnsignedInABase::Base base;
	long osFlags = os.flags();
	if (osFlags & os.dec)
		base = 10;
	else if (osFlags & os.hex) {
		base = 16;
		if (osFlags & os.showbase)
			os << "0x";
	} else if (osFlags & os.oct) {
		base = 8;
		if (osFlags & os.showbase)
			os << '0';
	} else
		throw "std::ostream << BigUnsigned: Could not determine the desired base from output-stream flags";
	std::string s = std::string(BigUnsignedInABase(x, base));
	os << s;
	return os;
}
std::ostream &operator <<(std::ostream &os, const BigInteger &x) {
	if (x.getSign() == BigInteger::negative)	os << '-';
	os << x.getMagnitude();
	return os;
}
BigInteger fibo[5010];
int main()
{
	int input;
	fibo[0] = 0;
	fibo[1] = 1;
	for(int i=2 ; i<5001 ; ++i)
		fibo[i] = fibo[i-1]+fibo[i-2];
	while(cin>>input)		cout<<"The Fibonacci number for "<<input<<" is "<<fibo[input]<<endl;
	return 0;
}