__BIGINT_THIS_FILE_IS( "mul.js", "v0.5 beta 9", "2003-12-28" );

//////////////////////////////////////////////////////////////////////////////////////


Bigint.mul = function( number1, number2 ) {
	var bigNumber1 = Bigint.serio( number1 );
	var bigNumber2 = Bigint.serio( number2 );

	if( bigNumber1.isZero() || bigNumber2.isZero() ) return ( new Bigint(0) );

	// Now both are non-zero (even if sign = 0 )

	var bigResult = Bigint._mul( bigNumber1, bigNumber2 );

	if( bigNumber1.sign < 0 && bigNumber2.sign >= 0 ) {
		bigResult.sign = (-1);
	} else if( bigNumber1.sign >= 0 && bigNumber2.sign < 0 ) {
		bigResult.sign = (-1);
	} else {
		bigResult.sign = (+1);
	}
	return bigResult;
}


Bigint.mulmod = function( number1, number2, modulus ) {
	var bigNumber1 = Bigint.serio( number1 );
	var bigNumber2 = Bigint.serio( number2 );
	var bigModulus = Bigint.serio( modulus );
	var bigProduct = Bigint._mul( bigNumber1, bigNumber2 );
	return Bigint._mod( bigProduct, bigModulus );
}

// 2 small numbers to small number
Bigint._mulmod32 = function( int1, int2 ) {
	//var al = int1 % __BIGINT_2E16;
	var al = int1 & 0xFFFF;
	var ah = int1 >>> 16;
	var bl = int2 & 0xFFFF;
	var bh = int2 >>> 16;
	return ( al*bl + (((( al*bh + ah*bl ) & 0xFFFF) << 16 ) >>> 0 ) ) >>> 0;
}



Bigint._mul = function( bigNumber1, bigNumber2 ) {

	var bigResult = new Bigint();

	for( var i = 0; i < bigNumber1.table.length; i++ ) {
		for( var j = 0; j < bigNumber2.table.length; j++ ) {

			var nWork = bigNumber1.table[i] * bigNumber2.table[j];
			var nLow = nWork % __BIGINT_BIG_UNIT;
			var nHigh = ( nWork - nLow ) / __BIGINT_BIG_UNIT;

/*
			var strWork = bigNumber1.table[i] * bigNumber2.table[j] + "";
			var nLow = strWork.slice( -7 ) - 0;
			var nHigh = strWork.slice( 0, -7 ) - 0;
*/

			if( bigResult.table[i+j] ) bigResult.table[i+j] += nLow;
			else bigResult.table[i+j] = nLow;

			if( nHigh ) {
				if( bigResult.table[i+j+1] ) bigResult.table[i+j+1] += nHigh;
				else bigResult.table[i+j+1] = nHigh;
			}
		}
	}

	var flag = 0;
	for( var i = 0; i < bigResult.table.length; i++ ) {
		bigResult.table[i] += flag;
		var number = bigResult.table[i];
		if( number >= __BIGINT_BIG_UNIT ) {
			bigResult.table[i] = number % __BIGINT_BIG_UNIT;
			flag = ( number - bigResult.table[i] ) / __BIGINT_BIG_UNIT;
		} else {
			flag = 0;
		}
	}

	if( flag ) {
		bigResult.table[i] = flag;
	}


//_debug("_mul: " + bigNumber1 +" * "+ bigNumber2 +" = "+ bigResult);

	return bigResult;
}

Bigint.square = function( input ) {
	var bigNumber = Bigint.serio( input );
	return Bigint._square( bigNumber );
}

Bigint._square = function( bigNumber ) {
	var tmp, nLow, nHigh, nSuperHigh;
	var Result = new Bigint();
	for( var i = 0; i < bigNumber.table.length; i++ ) {
		for( var j = i; j < bigNumber.table.length; j++ ) {
			tmp = bigNumber.table[i] * bigNumber.table[j];
			if( i !== j ) tmp *= 2;
			nLow = tmp % __BIGINT_BIG_UNIT;
			nHigh = ( tmp - nLow ) / __BIGINT_BIG_UNIT;
			if( nHigh >= __BIGINT_BIG_UNIT ) {
				nHigh -= __BIGINT_BIG_UNIT;
				nSuperHigh = 1;
			} else {
				nSuperHigh = 0;
			}

			if( Result.table[i+j] ) Result.table[i+j] += nLow;
			else Result.table[i+j] = nLow;
			
			if( nHigh > 0 ) {
				if( Result.table[i+j+1] ) Result.table[i+j+1] += nHigh;
				else Result.table[i+j+1] = nHigh;
			}
			if( nSuperHigh ) {
				if( Result.table[i+j+2] ) Result.table[i+j+2]++;
				else Result.table[i+j+2] = 1;
			}
		}
	}

	var lastIndex = Result.table.length - 1;
	for( var i = 0; i <= lastIndex; i++ ) {
		tmp = Result.table[i];
		if( tmp >= __BIGINT_BIG_UNIT) {
			Result.table[i] = tmp % __BIGINT_BIG_UNIT;
			if( i < lastIndex ) Result.table[i+1] += ( tmp - Result.table[i] ) / __BIGINT_BIG_UNIT;
			else Result.table[i+1] = ( tmp - Result.table[i] ) / __BIGINT_BIG_UNIT;
		}
	}

	return Result;
}



Bigint.prototype.setMultiplicationTable = function() {

	var strBigNumber =  this.toDecimalString();

	this.multipliedBy = new Array(10);
	this.multipliedBy[ 0 ] = "0";
	this.multipliedBy[ 1 ] = strBigNumber;

	var unit = 14;
	var UNIT = Math.pow( 10 , unit );

	var tableSize = Math.ceil( strBigNumber.length / unit );
	var tmpTable = new Array( tableSize );

	var lastLength = strBigNumber.length % unit;
	if( lastLength === 0 ) lastLength = unit;

	tmpTable[ tableSize-1 ] = strBigNumber.substr( 0 , lastLength );

	var pos = lastLength;
	for( var i = tableSize-2; i >= 0; i-- , pos += unit ) {
		tmpTable[i] = strBigNumber.substr( pos , unit ) - 0;
	}

	for( var i = 2; i <= 9; i++ ) {
		var workTable = new Array();
		var flag = 0;
		for( var j = 0; j < tmpTable.length; j++ ) {
			var number = tmpTable[j] * i + flag;
			if( number >= UNIT ) {
				workTable[j] = number % UNIT;
				flag = ( number - workTable[j] ) / UNIT;
			} else {
				workTable[j] = number;
				flag = 0;
			}
			workTable[j] += "";
			if( j < tmpTable.length - 1 || flag ) {
				while( workTable[j].length < unit ) workTable[j] = "0" + workTable[j];
			}
		}
		if( flag ) workTable[j] = flag + "";
		workTable.reverse();
		this.multipliedBy[i] = workTable.join("");
	}
}



Bigint.pow = function( base, power ) {
	var bigBase = Bigint.serio( base );
	var bigPower = Bigint.serio( power );

	if( bigPower.isZero() ) return new Bigint(1);
	else if( bigBase.isZero() ) return new Bigint(0);

	if( bigPower.sign < 0 ) {
		if( bigBase.isEqualTo(1) ) return new Bigint(1);
		else return new Bigint(0);
	}

	if( __BIGINT_SAFE_MODE ) {
		var nBase = bigBase.toDecimalString();
		var nPower = bigPower.toDecimalString();
		var estimatedDigits = Math.ceil( Bigint.log10( nBase ) * nPower );
		if( estimatedDigits > 5000 ) {
			var message = "Bigint.pow: " + nBase + "^" + nPower;
			message += " will be " + estimatedDigits + "-digit. Maybe time-consuming.";
			message += " Continue?"
			if( !confirm( message ) ) return void 0;
		}
	}

	var bigResult = Bigint._pow( bigBase, bigPower );

	if( bigBase.sign < 0 && bigPower.isOdd() ) bigResult.sign = (-1);
	else bigResult.sign = (+1);
	return bigResult;
}




Bigint._pow = function( bigBase, bigPower ) {
	var binaryString = bigPower.toBinaryString();
	var lastIndex = binaryString.length - 1;
	var bigWork = bigBase.copy();
	var bigResult = ( binaryString.charAt( lastIndex ) === "1" )? bigBase.copy() : ( new Bigint(1) ) ;
	for( var i = lastIndex - 1; i >= 0; i-- ) {
		bigWork = Bigint.square( bigWork );
		if( binaryString.charAt(i) === "1" ) {
			bigResult = Bigint.mul( bigResult, bigWork );
		}
	}
	return bigResult;
}


Bigint.powmod = function( base, power, modulus ) {
	var bigBase = Bigint.serio( base );
	var bigPower = Bigint.serio( power );
	var bigModulus = Bigint.serio( modulus );

	return Bigint._powmod( bigBase, bigPower, bigModulus );
}


Bigint._powmod = function( bigBase, bigPower, bigModulus ) {
	var binaryString = bigPower.toBinaryString();
	var lastIndex = binaryString.length - 1;
	var bigWork = bigBase;
	var bigResult = ( binaryString.charAt( lastIndex ) === "1" )? bigBase.copy() : ( new Bigint(1) );
	for( var i=lastIndex - 1; i >= 0; i-- ) {
		bigWork = Bigint._square( bigWork );
		bigWork = Bigint._mod( bigWork, bigModulus );
		if( binaryString.charAt(i) === "1" ) {
			bigResult = Bigint._mul( bigResult, bigWork );
			bigResult = Bigint._mod( bigResult, bigModulus );
		}
	}
	return bigResult;
}

Bigint._powmod_typeF = function( bigBase, bigPower, bigModulus ) {
	var binaryString = bigPower.toBinaryString();
	var lastIndex = binaryString.length - 1;
	var bigWork = bigBase;
	var bigResult = ( binaryString.charAt( lastIndex ) === "1" )? bigBase.copy() : ( new Bigint(1) );
	for( var i=lastIndex - 1; i >= 0; i-- ) {
		bigWork = Bigint._mod_typeF( Bigint._square( bigWork ), bigModulus );
		if( binaryString.charAt(i) === "1" ) {
			bigResult = Bigint._mod_typeF( Bigint._mul( bigResult, bigWork ), bigModulus );
		}
		if( i % 2 === 0 ) Bigint._progress("*");
	}
	return bigResult;
}


Bigint._sqmod = function( bigBase, bigModulus ) {
	var bigSquare = Bigint._square( bigBase );
	return Bigint._mod( bigSquare, bigModulus );
}

Bigint.factorial = function( input ) {
	if( input === void 0 || input === "" ) {
		return Bigint._error( "factorial", "input void" );
	}

	var smallNumber;

	if( input.isBigint ) smallNumber = input.toDecimalString();
	else smallNumber = input - 0;

	if( isNaN( smallNumber ) || Math.floor( smallNumber ) !== smallNumber || smallNumber < 0 ) {
		return Bigint._error( "factorial", "bad input: " + input );
	} else if( smallNumber === 0 ) {
		return new Bigint(1);
	} else if( smallNumber <= 900 ) {
		return Bigint._factorial( smallNumber, 13 );
	} else if( smallNumber <= 9007 ) {
		return Bigint._factorial( smallNumber, 12 );
	} else if( smallNumber <= 90071 ) {
		var message = "Trying to calculate factorial(" + smallNumber + "). ";
			message += "Are you sure?"
		if( confirm( message ) ) return Bigint._factorial_gt_9007( smallNumber );
	} else {
		return Bigint._error( "factorial" , "input too big: " + input );
	}

	return void 0;
}

Bigint._factorial = function( smallNumber, unit ) {
	var UNIT = ( unit === 13 )? __BIGINT_E13 : __BIGINT_E12 ;
	var PADDING = ( unit === 13 )? Bigint._padding13 : Bigint._padding12 ;
	var myTable = [ 1 ];
	for( var n = 2; n <= smallNumber; n++ ) {
		var nTableSize = myTable.length;
		var nOverflow = 0;
		var nWork;
		var i;
		for( i = 0; i < nTableSize; i++ ) {
			nWork = nOverflow + myTable[i] * n;
			myTable[i] = nWork % UNIT;
			nOverflow =  ( nWork - myTable[i] ) / UNIT;
		}
		if(nOverflow) myTable[i] = nOverflow;
	}
	var lastIndex = myTable.length - 1;
	var strResult = myTable[ lastIndex ] + "";

	for( var i = lastIndex - 1; i>=0; i-- ) {
		strResult += PADDING( myTable[ i ] + "" );
	}
	return new Bigint( strResult );
}

Bigint._factorial_gt_9007 = function( smallNumber ) {
	var UNIT = Math.pow( 10, 11 );
	var PADDING = Bigint._padding11;
	var myTable = new Array(2883);
	var strFactorial_9007 = Bigint._factorial( 9007, 12 ).toDecimalString(); // 31710-digit
	myTable[2882] = strFactorial_9007.substr( 0 , 8 );
	var pos = 8;
	for( var i = 2881; i >= 0; i-- , pos+=11 ) {
		myTable[ i ] = strFactorial_9007.substr( pos , 11 );
	}

	for( var n = 9008; n <= smallNumber; n++ ) {
		var nTableSize = myTable.length;
		var nOverflow = 0;
		var nWork;
		var i;
		for( i = 0; i < nTableSize; i++ ) {
			nWork = nOverflow + myTable[i] * n;
			myTable[i] = nWork % UNIT;
			nOverflow =  ( nWork - myTable[i] ) / UNIT;
		}
		if(nOverflow) myTable[i] = nOverflow;
	}
	var lastIndex = myTable.length - 1;
	var strResult = myTable[ lastIndex ] + "";

	for( var i = lastIndex - 1; i>=0; i-- ) {
		strResult += PADDING( myTable[ i ] + "" );
	}
	return new Bigint( strResult );
}