function BigInt(len, sign)
{
	var i, x, need_init;
	if(sign==null) sign=1;
	this.toString = function ()
	{
		var s="",i, j, t, ds, c;
		i = this.len;
		if(i == 0) return "0";
		if(i == 1 && ! this.digits[0]) return "0";
		
		j = Math.floor((2 * 8 * i * 241) / 800) + 2;
		t = this.clone();
		ds = t.digits;
	
		while (i && j)
		{
			var k = i, num = 0;
			while (k--)
			{
				num = (num << 16) + ds[k];
				if(num < 0) num += 4294967296;
				ds[k] = Math.floor(num/10000);
				num %= 10000;
			}
			
			if (ds[i-1] == 0) i--;
			k = 4;
			while (k--)
			{
				c = (num % 10);
				s = "0123456789abcdef".charAt(c) + s;
				--j;
				num = Math.floor(num / 10);
				if (i == 0 && num == 0) break;
			}
		}
		
		i = 0;
		while(i < s.length && s.charAt(i) == "0") i++ ;
		if(i) s = s.substring(i, s.length);
		if(! this.sign) s = "-"+s;
		return s;
	};
	this.clone = function ()
	{
		var i,x=new BigInt(this.len, this.sign);
		for(i = 0; i < this.len; i++ ) x.digits[i] = this.digits[i];
		return x;
	};
	this.trim=function(){
	   var len = this.len,ds = this.digits;
	   while(len--&&!ds[len]);
	   this.len = ++len;
	   return this;
	};
	this.neg=function(){
		var z = this.clone();
		z.sign=!this.sign;
		return z.trim();
	};
	this.internal_add=function(x, y, sign) {
		var z,num,i, len;
		sign = (sign == y.sign);
		if (x.sign != sign) { if (sign) return this.internal_sub(y, x); return this.internal_sub(x, y); }
		
		if (x.len > y.len) { len = x.len + 1; z = x; x = y; y = z; }
		else len = y.len + 1;
		z = new BigInt(len, sign);
		
		len = x.len;
		for (i = 0, num = 0; i < len; i++ )
		{
		  num += x.digits[i] + y.digits[i];
		  z.digits[i] = (num & 0xffff);
		  num >>>= 16;
		}
		len = y.len;
		while (num && i < len)
		{
		  num += y.digits[i];
		  z.digits[i++ ] = (num & 0xffff);
		  num >>>= 16;
		}
		while (i < len)
		{
		  z.digits[i] = y.digits[i];
		  i++ ;
		}
		z.digits[i] = (num & 0xffff);
		return z.trim();
	};
	this.internal_sub=function(x, y) {
		var z = 0,zds,num,i;
		
		i = x.len;
		if (x.len < y.len) { z = x; x = y; y = z; }
		else if (x.len == y.len)
		{
		  while (i > 0)
		  {
			 i -- ;
			 if (x.digits[i] > y.digits[i]) break;
			 if (x.digits[i] < y.digits[i]) { z = x; x = y; y = z; break; }
		  }
		}
		
		z = new BigInt(x.len, (z == 0) ? 1 : 0);
		zds = z.digits;
		
		for (i = 0, num = 0; i < y.len; i++ )
		{
		  num += x.digits[i] - y.digits[i];
		  zds[i] = (num & 0xffff);
		  num >>>= 16;
		}
		while (num && i < x.len)
		{
		  num += x.digits[i];
		  zds[i++ ] = (num & 0xffff);
		  num >>>= 16;
		}
		while (i < x.len)
		{
		  zds[i] = x.digits[i];
		  i++ ;
		}
		return z.trim();
	};
	this.add=function(y) {return this.internal_add(this,Convert.from(y), 1);};
	this.subtract=function(y) {return this.internal_add(this, Convert.from(y), 0);};
	this.multi=function(y){
	   var i,j,n=0,z,dd,ee,x=this;
	   y = Convert.from(y);
	   j = x.len + y.len + 1;
	   z = new BigInt(j, x.sign == y.sign);
	
	   var xds = x.digits, yds = y.digits, zds = z.digits, ylen = y.len;
	   while (j--) zds[j] = 0;
	   for (i = 0; i < x.len; i++ )
	   {
		  dd = xds[i];
		  if (dd == 0) continue;
		  n = 0;
		  for (j = 0; j < ylen; j ++ )
		  {
			 ee = n + dd * yds[j];
			 n = zds[i + j] + ee;
			 if (ee)
			 zds[i + j] = (n & 0xffff);
			 n >>>= 16;
		  }
		  if (n) zds[i + j] = n;
	   }
	   return z.trim();
	};
	this.pow=function(p){
		if(p==0) return "1";
		var z=this;
		for(var i=1;i<p;i++) z=z.multi(this);
		return z;
	};
	this.divide=function(y, mod){
		y=Convert.from(y);
		var x=this, nx = x.len, ny = y.len, i, j, yy, z, xds, yds, zds, tds, t2, num, dd, q, ee, mod, div;
		yds = y.digits;
		if (ny == 0 && yds[0] == 0) return null; // Division by zero
		if (nx < ny || nx == ny && x.digits[nx - 1] < y.digits[ny - 1])
		{
			if (mod) return x.trim();
			return BigInt(1, 1);
		}
		xds = x.digits;
		if (ny == 1)
		{
		  dd = yds[0]; z = x.clone(); zds = z.digits; t2 = 0; i = nx;
		  while (i -- )

		  {
			 t2 = t2 * 65536 + zds[i];
			 zds[i] = (t2 / dd) & 0xffff;
			 t2 %= dd;
		  }
		  z.sign = (x.sign == y.sign);
		  if (mod)
		  {
		  	if (!x.sign) t2 = - t2;
			if (x.sign != y.sign) t2 = t2 + yds[0] * (y.sign ? 1 : - 1);
			return Convert.fromInt(t2);
		  }
		  return z.trim();
		}
		z = new BigInt(nx == ny ? nx + 2 : nx + 1, x.sign == y.sign);
		zds = z.digits;
		if (nx == ny) zds[nx + 1] = 0;
		while (!yds[ny - 1]) ny -- ;
		if ((dd = ((65536 / (yds[ny - 1] + 1)) & 0xffff)) != 1)
		{
		  yy = y.clone(); tds = yy.digits; j = 0; num = 0;
		  while (j < ny)
		  {
			 num += yds[j] * dd;
			 tds[j ++ ] = num & 0xffff;
			 num >>= 16;
		  }
		  yds = tds; j = 0; num = 0;
		  while (j < nx)
		  {
			 num += xds[j] * dd;
			 zds[j ++ ] = num & 0xffff;
			 num >>= 16;
		  }
		  zds[j] = num & 0xffff;
		}
		else
		{
		  zds[nx] = 0;
		  j = nx;
		  while (j -- ) zds[j] = xds[j];
		}
		j = nx == ny ? nx + 1 : nx;
		do
		{
		  if (zds[j] ==  yds[ny - 1]) q = 65535;
		  else q = ((zds[j] * 65536 + zds[j - 1]) / yds[ny - 1]) & 0xffff;
		  if (q)
		  {
			 i = 0; num = 0; t2 = 0;
			 do // multiply and subtract
			 {
				t2 += yds[i] * q;
				ee = num - (t2 & 0xffff);
				num = zds[j - ny + i] + ee;
				if (ee) zds[j - ny + i] = num & 0xffff;
				num >>= 16;
				t2 >>>= 16;
			 }
			 while ( ++ i < ny);
			 num += zds[j - ny + i] - t2;
			 while (num) // borrow from high digit; don't update
			 {
				i = 0; num = 0; q -- ;
				do
				{
				   ee = num + yds[i];
				   num = zds[j - ny + i] + ee;
				   if (ee) zds[j - ny + i] = num & 0xffff;
				   num >>= 16;
				}
				while ( ++ i < ny);
				num -- ;
			 }
		  }
		  zds[j] = q;
		}
		while ( --j >= ny);
		if (mod) // just normalize remainder
		{
		  mod = z.clone();
		  if (dd)
		  {
			 zds = mod.digits; t2 = 0; i = ny;
			 while (i -- )
			 {
				t2 = (t2 * 65536) + zds[i];
				zds[i] = (t2 / dd) & 0xffff;
				t2 %= dd;
			 }
		  }
		  mod.len = ny;
		  mod.sign = x.sign;
		  if (x.sign != y.sign) return x.internal_add(mod, y, 1);
		  return mod.trim();
		}
		
		div = z.clone();
		zds = div.digits;
		j = (nx == ny ? nx + 2 : nx + 1) - ny;
		for (i = 0; i < j; i++ ) zds[i] = zds[i + ny];
		div.len = i;
		return div.trim();
	};
	this.mod=function(y){return this.divide(y,1);};
	this.compare=function(y) {
		if(y==this) return 0;
		var x=this,xlen = x.len;
		y = Convert.from(y);	
		if(x.sign != y.sign) { if(x.sign) return 1; return - 1; }
		
		if (xlen < y.len) return (x.sign) ? - 1 : 1;
		if (xlen > y.len) return (x.sign) ? 1 : - 1;
		
		while(xlen -- && (x.digits[xlen] == y.digits[xlen]));
		if ( - 1 == xlen) return 0;
		return (x.digits[xlen] > y.digits[xlen]) ? (x.sign ? 1 : - 1) : (x.sign ? - 1 : 1);
	};
	this.toNumber=function(x){
		var d = 0.0, i=this.len, ds = this.digits;
		
		while (i -- ) d = ds[i] + 65536.0 * d;
		if (!this.sign) d = - d;
		return d;
	};
	
	if(BigInt.arguments.length == 0)
	{
		this.sign = true;
		this.len = len = 1;
		this.digits = new Array(1);
		need_init = true;
	}
	else if(BigInt.arguments.length == 1)
	{
		x = Convert.from(BigInt.arguments[0]);
		if(x == BigInt.arguments[0])
		x = x.clone();
		this.sign = x.sign;
		this.len = x.len;
		this.digits = x.digits;
		need_init = false;
	}
	else
	{
		this.sign = (sign ? true : false);
		this.len = len;
		this.digits = new Array(len);
		need_init = true;
	}
	
	if(need_init) { for(i = 0; i < len; i++ ) this.digits[i] = 0; }
}
var Convert={
fromInt:function(n)
{
	var sign, big, i;
	if(n < 0){n = - n;sign = false;}
	else sign = true;
	n &= 0x7fffffff;
	if(n <= 0xffff){ big = new BigInt(1, 1); big.digits[0] = n; }
	else { big = new BigInt(2, 1); big.digits[0] = (n & 0xffff); big.digits[1] = ((n >> 16) & 0xffff); }
	return big;
},
fromString:function(s)
{
	var pos,sign = true,c,len,z,zds,num,i,blen = 1;
	s += "@";
	pos = 0;
	if(s.charAt(pos) == "+") pos++ ;
	else if (s.charAt(pos) == "-") { pos++ ; sign = false; }
	
	if (s.charAt(pos) == "@") return null;
	
	while (s.charAt(pos) == "0") pos++ ;
	if (s.charAt(pos) == "@") pos -- ;
	len = 4 * (s.length - pos);
	
	len = (len >> 4) + 1;
	z = new BigInt(len, sign);
	zds = z.digits;
	
	while(true)
	{
		c = s.charAt(pos++ );
		if(c == "@") break;
		c=parseInt(c);
		if(isNaN(c)) break;
		
		i = 0; num = c;
		while(true)
		{
			while (i < blen)
			{	num += zds[i] * 10;
				zds[i++] = (num & 0xffff);
				num >>>= 16;
			}
			if (num) { blen ++ ; continue; }
			break;
		}
	}
	return z.trim();
},
from:function(x)
{
	if(typeof(x) == "object")
	{
	  if(x.constructor == BigInt) return x;
	  return BigInt(1, 1);
	}
	if(typeof(x) == "string") return Convert.fromString(x);
	if(typeof(x) == "number")
	{
	  var i, x1, x2, fpt, np;
	  if( - 2147483647 <= x && x <= 2147483647) return Convert.fromInt(x);
	  x = x + "";
	  i = x.indexOf("e", 0);
	  if(i == - 1) return Convert.fromString(x);
	  x1 = x.substr(0, i);
	  x2 = x.substr(i + 2, x.length - (i + 2));
	  fpt = x1.indexOf(".", 0);
	  if(fpt != - 1)
	  {
		 np = x1.length - (fpt + 1);
		 x1 = x1.substr(0, fpt) + x1.substr(fpt + 1, np);
		 x2 = parseInt(x2) - np;
	  }
	  else x2 = parseInt(x2);
	  while(x2 -- > 0) x1 += "0";
	  return Convert.fromString(x1);
	}
	return BigInt(1, 1);
}
};