// Big numbers
// Author: Mohit Jain
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <exception>
using namespace std;
#define BIGNUM_NAMESPACE_START namespace bignums {
#define BIGNUM_NAMESPACE_END }


BIGNUM_NAMESPACE_START

class bignum_exception: public std::exception {
public:
  bignum_exception()
  {}
};

#define THROW_EXCEPTION(X) throw bignum_exception()

class COneDigitOperations {
  char num, carry;
  struct OperationMaps {
    char plusArrayN[256][256], plusArrayC[256][256];
    char mulArrayN[256][256],  mulArrayC[256][256];
    OperationMaps() {
      static const char numToChar[] = "0123456789";
      for(int i = 0, ic = '0'; i < 10; ++i, ++ic)
      for(int j = 0, jc = '0'; j < 10; ++j, ++jc) {
        const int s = i + j, m = i * j;
        plusArrayN[ic][jc] = plusArrayN[i][j] = numToChar[s % 10];
        plusArrayC[ic][jc] = plusArrayC[i][j] = numToChar[s / 10];
        mulArrayN [ic][jc] = mulArrayN [i][j] = numToChar[m % 10];
        mulArrayC [ic][jc] = mulArrayC [i][j] = numToChar[m / 10];
      }
    }
  };
  static OperationMaps m;
public:
  enum EBigOperations { ePlus, eMultiply };
  COneDigitOperations(char a_, char b_, EBigOperations op_, char c_ = '0') {
    int a = a_ - '0';
    int b = b_ - '0';
	if(a > 9) a -= '0';
	if(b > 9) b -= '0';
	if(a < 0 || a > 9 || b < 0 || b > 9) {
		THROW_EXCEPTION("Digit out of range");
	}

    switch (op_) {
    case ePlus:
      num   = m.plusArrayN[a][b];
      carry = m.plusArrayC[a][b];
      if(c_ != '0' && num++ == '9') ++carry, num = '0';
      break;
    case eMultiply:
      num   = m.mulArrayN[a][b];
      carry = m.mulArrayC[a][b]; {
        carry = m.plusArrayN[ int(m.plusArrayC[ int(num) ][ int(c_) ]) ][ int(carry) ];
        num   = m.plusArrayN[ int(num) ][ int(c_) ];
      }
      break;
    default:
      THROW_EXCEPTION("Operation not supported");
    }
  }
  char getNum() const { return num; }
  char getCarry() const { return carry; }
};
COneDigitOperations::OperationMaps COneDigitOperations::m;	// static

class DecimalUnsignedBigNum {
  string num;
private:
  DecimalUnsignedBigNum &multiplyWith10() {
    num = "0" + num;
    return *this;
  }
  void prepend(string &s, string::size_type sz) {
    s += string(sz, '0');
  }
  void trim(string &s);		// Remove all trailing zeroes, if string is empty, set it to "0"
public:
  DecimalUnsignedBigNum() : num("0") {}
  DecimalUnsignedBigNum(unsigned int i) {
    stringstream ss;
    ss << i;
    ss.str().swap( num );
	std::reverse( num.begin(), num.end() );
  }
  // Copy constructor, assignation operator, comparision operators (<,= etc)
  string toStr() const {
    string rev(num);               // I did not overload << because,
    reverse( rev.begin(), rev.end() );   // user may expect me to handle
    return rev;                          // hex, width, fill etc
  }
  // operator +, -, /, *, +=, -= ... for int and DecimalUnsignedBigNum
  DecimalUnsignedBigNum &operator +=(const DecimalUnsignedBigNum &t) {
    string that(t.num);
    if( num.size() > that.size() ) prepend( that, num.size() - that.size() );
    else prepend( num, that.size() - num.size() );
    char currentCarry = '0';
    for(string::iterator it = num.begin(), jt = that.begin();
      it != num.end();
      ++it, ++jt) {
    COneDigitOperations d(*it, *jt, COneDigitOperations::ePlus, currentCarry);
    *it = d.getNum();
    currentCarry = d.getCarry();
    }
    if(currentCarry != '0') num += currentCarry;
	return *this;
  }
  DecimalUnsignedBigNum &operator *=(unsigned int t) {
    DecimalUnsignedBigNum result;
    while(0 != t) {
      char currentCarry = '0';
      char curNum = "0123456789"[t % 10];
      t /= 10;
      DecimalUnsignedBigNum temp;
      temp.num.clear();
      for(string::iterator it = num.begin(); it != num.end(); ++it) {
        COneDigitOperations m(*it, curNum, COneDigitOperations::eMultiply, currentCarry);
        temp.num += m.getNum();
		currentCarry = m.getCarry();
	  }
      if('0' != currentCarry) temp.num += currentCarry;
      result += temp;
      this->multiplyWith10();
	}
	return (*this = result);
  }
};
BIGNUM_NAMESPACE_END

int main() {
  bignums::DecimalUnsignedBigNum f100 = 1U;
  for(int i = 2; i <= 100; ++i) {
    f100 *= i;
	//cout << i << "! = " << f100.toStr() << endl;
  }
  const string expected("93326215443944152681699238856266700490715968264381621"
	  "46859296389521759999322991560894146397615651828625369792082722375825118"
	  "5210916864000000000000000000000000");
  if( expected != f100.toStr() ) cout << "Expected = " << endl << expected << endl;
  cout << f100.toStr() << endl;
  return 0;
}

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000