function numArray(str){
	var len = str.length;
	var n = (len - (str.charAt(0) == "-" ? 1 : 0)) % 5;
	var reg = new RegExp("^\\-?\\d{" + (n == 0 ? 5 : n) + "}|\\d{5}", "g");
	var num = str.match(reg);
	num.reverse();
	var i;

	if (str.charAt(0) == "-") {
		for (i = 0; i < num.length - 1; i++) {
			num[i] = -Number(num[i]);
		}
		num[i] = Number(num[i]);
	}
	else {
		for (i = 0; i < num.length; i++) {
			num[i] = Number(num[i]);
		}
	}
	return num;
}

function arrayToString(n){
	var num = copyNum(n);
	var len = num.length;
	var sign = num[len - 1] < 0 ? -1 : 1;
	var i;

	for (i = 0; i < num.length - 1; i++) {
		num[i] = (num[i] * sign >= 10000 ? "" : num[i] * sign >= 1000 ? "0" : num[i] * sign >= 100 ? "00" : num[i] * sign >= 10 ? "000" : "0000") + (sign * num[i]).toString();
	}
	num[i] = num[i].toString();
	num.reverse();
	return num.join("");
}

function InfAdd(a, b){
	var i, len;
	var c = new Array();
	var n = 0, sign = 1;

	if (InfComp(InfAbs(a), InfAbs(b)) >= 0) {
		len = a.length;
	}
	else {
		len = b.length;
	}
	for (i = 0; i < len; i++) { // 加算
		c[i] = a[i] ? a[i] + (b[i] ? b[i] : 0) : b[i];
	}
	for (i = len - 1; i >= 0; i--){ // 解の符号
		if(c[i] > 0) {
			sign = 1;
			break;
		}
		else if(c[i] < 0) {
			sign = -1;
			break;
		}
		len--;
	}
	c.length = len = len ? len : 1;

	for (i = 0; i < len; i++) { // 繰り上げ、繰り下げ
		c[i] += n;
		if(c[i] * sign >= 100000){
			c[i] -= sign * 100000;
			n = sign;
		}
		else if(c[i] * sign < 0) {
			c[i] += sign * 100000;
			n = -sign;
		}
		else {
			n = 0;
		}
	}
	if (n) {
		c[len++] = n;
	}

	for (i = len - 1; i > 1; i--) {
		if(c[i]) break;
		len--;
	}
	c.length = len;
	return c;
}

function InfSub(a, b){
	return InfAdd(a, InfReverse(b));
}

function InfMult(a, b){
	var lenA = a.length;
	var lenB = b.length;
	var lenC = lenA + lenB - 1;
	var c = new Array(lenC);
	var sign = (a[lenA - 1] > 0) == (b[lenB - 1] > 0) ? 1 : -1;
	var i, j;
	var n = 0;

	for (i = lenC - 1; i >= 0; i--) {
		c[i] = 0;
	}

	for (i = 0; i < lenA; i++) {
		for (j = 0; j < lenB; j++) {
			c[i + j] += a[i] * b[j] + n;
			if (c[i + j] * sign >= 100000) {
				n = sign * Math.floor(c[i + j] * sign / 100000);
				c[i + j] %= 100000;
			}
			else n = 0;
		}
		if (n) {
			c[i + j] = n;
			n = 0;
		}
	}
	if (!c[lenC]) {
		for (i = lenC - 1; i > 0; i--) {
			if (c[i]) break;
			lenC--;
		}
		c.length = lenC;
	}
	return c;
}

function InfDivMod(a, b){
	var lenA = a.length;
	var lenB = b.length;
	var sign1 = a[lenA - 1] * b[lenB - 1] < 0 ? -1 : 1;
	var sign2 = a[lenA - 1] < 0 ? -1 : 1;
	var div = [0];
	var mod = copyNum(a);
	var b2 = b[lenB - 1] * 100000 + (lenB - 1 ? b[lenB - 2] : 0);
	var i, j, n, ary;

	for (i = lenA - lenB; i >= 0; i--) {
		div[i] = sign1 * Math.floor(sign1 * (
			(mod[i + lenB] ? mod[i + lenB] * 10000000000 : 0)
			+ mod[i + lenB - 1] * 100000
			+ (i + lenB ? mod[i + lenB - 1] : 0)
		) / b2);
		if (div[i]) {
			ary = InfMult(b, [div[i]]);
			for (j = n = 0; j < ary.length; j++) {
				if ((mod[i + j] -= ary[j] + n) * sign2 < 0) {
					n = sign2;
				}
				else {
					n = 0;
				}
			}
			if (n && mod[i + j]) {
				mod[i + j] = 0;
			}
			else if (n && !mod[lenB + i]) {
				div[i] -= sign1;
				for (j = n = 0; j < lenB; j++) {
					if ((mod[i + j] += sign2 * Math.abs(b[j]) + n) * sign2 < 0) {
						n = sign2;
					}
					else {
						n = 0;
					}
				}
			}
			for (j = 0; j < lenB; j++) {
				if (mod[i + j] * sign2 < 0) {
					mod[i + j] += sign2 * 100000;
				}
			}
		}
	}
	for (i = lenB - 1; i > 0; i--) {
		if (mod[i]) break;
	}
	if (!div[lenA - lenB]) {
		div.length--;
	}
	mod.length = i + 1;
	return [div, mod];
}

function InfDiv(a, b) {
	return InfDivMod(a, b)[0]
}

function InfMod(a, b) {
	return InfDivMod(a, b)[1];
}

function InfPow(a, b) { // a ^ b
	if (b[b.length - 1] < 0) {
		if (InfComp(InfAbs(a), [1])) {
			return [0];
		}
		else if(a[0] == -1 && b[0] & 1) {
			return [-1];
		}
		else {
			return [1];
		}
	}

	var bin = "";
	var dec = copyNum(b);
	var pow = InfAbs(a);
	var len = dec.length;
	var lenBin, i;
	var n;

	while (len > 1 || dec[0] > 1) {
		n = 0;
		bin += (dec[0] & 1) ? "1" : "0";
		for (i = len - 1; i >= 0; i--) {
			dec[i] += n;
			n = (dec[i] & 1) * 100000;
			dec[i] >>= 1;
		}
		while (dec[len - 1] == 0 && len > 1) {
			len--;
		}
	}
	bin += dec[0] ? "1" : "0";
	lenBin = bin.length;

	dec = [1];
	i = 0;
	while (1) {
		if (bin.charAt(i) == "1") {
			dec = InfMult(dec, pow);
		}
		if (i < lenBin - 1) {
			pow = InfMult(pow, pow);
		}
		else {
			break;
		}
		i++;
	}
	if (a[a.length - 1] < 0 && b[0] & 1) {
		dec = InfReverse(dec);
	}

	return dec;
}

function InfFact(num){
	if (num[num.length - 1] < 0) {
		return [NaN];
	}

	var n = copyNum(num);
	var x = [1];

	while (n[0] > 1 || n.length > 1) {
		x = InfMult(n, x);
		n = InfSub(n, [1]);
	}

	return x;
}

function InfPerm(n, r) {
	if (n[n.length - 1] < 0 || r[r.length - 1] < 0 || InfComp(n, r) < 0) {
		return [NaN];
	}

	var comp = InfSub(n, r);
	var k = copyNum(n);
	var x = [1];

	while (InfComp(k, comp)) {
		x = InfMult(k, x);
		k = InfSub(k, [1]);
	}

	return x;
}



function InfComb(n, r) {
	if (InfComp(n, InfMult(r, [2])) < 0) {
		r = InfSub(n, r);
	}

	var fact = InfFact(r);
	var perm = InfPerm(n, r);

	return InfDiv(perm, fact);
}

function InfAbs(num){
	var len = num.length;
	if(num[len - 1] >= 0) return copyNum(num);
	else return InfReverse(num);
}

function InfReverse(num1) { // return -A
	var len = num1.length;
	var num2 = new Array(len);
	var i;
	for (i = 0; i < len; i++) {
		num2[i] = -num1[i];
	}
	return num2;
}

function InfComp(a, b){ // return A > B ? 1 : return A == B ? 0 : -1;
	var lenA = a.length;
	var lenB = b.length;
	var i;

	if (lenA > lenB) return 1;
	else if (lenA < lenB) return -1;

	for (i = lenA; i >= 0; i--){
		if (a[i] > b[i]) return 1;
		else if (a[i] < b[i]) return -1;
	}

	return 0;
}

function copyNum(num1) {
	var len = num1.length;
	var num2 = new Array(len);
	for (i = 0; i < len; i++) {
		num2[i] = num1[i];
	}

	return num2;
}