navigator = {};

var dbits;
var canary = 0xdeadbeefcafe;
var j_lm = ((canary & 0xffffff) == 0xefcafe);
function BigInteger(d, e, f) {
if (d != null) if ("number" == typeof d) this.fromNumber(d, e, f);
else if (e == null && "string" != typeof d) this.fromString(d, 256);
else this.fromString(d, e);
}
function nbi() {
return new BigInteger(null);
}
function am1(b, h, g, d, a, e) {
while (--e >= 0) {
    var f = h * this[b++] + g[d] + a;
    a = Math.floor(f / 0x4000000);
    g[d++] = f & 0x3ffffff;
}
return a;
}
function am2(d, p, o, e, a, k) {
var r = p & 0x7fff,
q = p >> 15;
while (--k >= 0) {
    var f = this[d] & 0x7fff;
    var b = this[d++] >> 15;
    var g = q * f + b * r;
    f = r * f + ((g & 0x7fff) << 15) + o[e] + (a & 0x3fffffff);
    a = (f >>> 30) + (g >>> 15) + q * b + (a >>> 30);
    o[e++] = f & 0x3fffffff;
}
return a;
}
function am3(d, p, o, e, a, k) {
var r = p & 0x3fff,
q = p >> 14;
while (--k >= 0) {
    var f = this[d] & 0x3fff;
    var b = this[d++] >> 14;
    var g = q * f + b * r;
    f = r * f + ((g & 0x3fff) << 14) + o[e] + a;
    a = (f >> 28) + (g >> 14) + q * b;
    o[e++] = f & 0xfffffff;
}
return a;
}
if (j_lm && (navigator.appName == "Microsoft Internet Explorer")) {
BigInteger.prototype.am = am2;
dbits = 30;
} else if (j_lm && (navigator.appName != "Netscape")) {
BigInteger.prototype.am = am1;
dbits = 26;
} else {
BigInteger.prototype.am = am3;
dbits = 28;
}
BigInteger.prototype.DB = dbits;
BigInteger.prototype.DM = ((1 << dbits) - 1);
BigInteger.prototype.DV = (1 << dbits);
var BI_FP = 52;
BigInteger.prototype.FV = Math.pow(2, BI_FP);
BigInteger.prototype.F1 = BI_FP - dbits;
BigInteger.prototype.F2 = 2 * dbits - BI_FP;
var BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz";
var BI_RC = new Array();
var rr, vv;
rr = "0".charCodeAt(0);
for (vv = 0; vv <= 9; ++vv) BI_RC[rr++] = vv;
rr = "a".charCodeAt(0);
for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
rr = "A".charCodeAt(0);
for (vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv;
function int2char(a) {
return BI_RM.charAt(a);
}
function intAt(d, b) {
var a = BI_RC[d.charCodeAt(b)];
return (a == null) ? -1 : a;
}
function bnpCopyTo(b) {
for (var a = this.t - 1; a >= 0; --a) b[a] = this[a];
b.t = this.t;
b.s = this.s;
}
function bnpFromInt(a) {
this.t = 1;
this.s = (a < 0) ? -1 : 0;
if (a > 0) this[0] = a;
else if (a < -1) this[0] = a + DV;
else this.t = 0;
}
function nbv(a) {
var b = nbi();
b.fromInt(a);
return b;
}
function bnpFromString(f, a) {
var d;
if (a == 16) d = 4;
else if (a == 8) d = 3;
else if (a == 256) d = 8;
else if (a == 2) d = 1;
else if (a == 32) d = 5;
else if (a == 4) d = 2;
else {
    this.fromRadix(f, a);
    return;
}
this.t = 0;
this.s = 0;
var c = f.length,
e = false,
g = 0;
while (--c >= 0) {
    var h = (d == 8) ? f[c] & 0xff: intAt(f, c);
    if (h < 0) {
        if (f.charAt(c) == "-") e = true;
        continue;
    }
    e = false;
    if (g == 0) this[this.t++] = h;
    else if (g + d > this.DB) {
        this[this.t - 1] |= (h & ((1 << (this.DB - g)) - 1)) << g;
        this[this.t++] = (h >> (this.DB - g));
    } else this[this.t - 1] |= h << g;
    g += d;
    if (g >= this.DB) g -= this.DB;
}
if (d == 8 && (f[0] & 0x80) != 0) {
    this.s = -1;
    if (g > 0) this[this.t - 1] |= ((1 << (this.DB - g)) - 1) << g;
}
this.clamp();
if (e) BigInteger.ZERO.subTo(this, this);
}
function bnpClamp() {
var a = this.s & this.DM;
while (this.t > 0 && this[this.t - 1] == a)--this.t;
}
function bnToString(a) {
if (this.s < 0) return "-" + this.negate().toString(a);
var f;
if (a == 16) f = 4;
else if (a == 8) f = 3;
else if (a == 2) f = 1;
else if (a == 32) f = 5;
else if (a == 4) f = 2;
else return this.toRadix(a);
var g = (1 << f) - 1,
c,
h = false,
l = "",
e = this.t;
var j = this.DB - (e * this.DB) % f;
if (e-->0) {
    if (j < this.DB && (c = this[e] >> j) > 0) {
        h = true;
        l = int2char(c);
    }
    while (e >= 0) {
        if (j < f) {
            c = (this[e] & ((1 << j) - 1)) << (f - j);
            c |= this[--e] >> (j += this.DB - f);
        } else {
            c = (this[e] >> (j -= f)) & g;
            if (j <= 0) {
                j += this.DB; --e;
            }
        }
        if (c > 0) h = true;
        if (h) l += int2char(c);
    }
}
return h ? l: "0";
}
function bnNegate() {
var a = nbi();
BigInteger.ZERO.subTo(this, a);
return a;
}
function bnAbs() {
return (this.s < 0) ? this.negate() : this;
}
function bnCompareTo(b) {
var d = this.s - b.s;
if (d != 0) return d;
var c = this.t;
d = c - b.t;
if (d != 0) return d;
while (--c >= 0) if ((d = this[c] - b[c]) != 0) return d;
return 0;
}
function nbits(c) {
var a = 1,
b;
if ((b = c >>> 16) != 0) {
    c = b;
    a += 16;
}
if ((b = c >> 8) != 0) {
    c = b;
    a += 8;
}
if ((b = c >> 4) != 0) {
    c = b;
    a += 4;
}
if ((b = c >> 2) != 0) {
    c = b;
    a += 2;
}
if ((b = c >> 1) != 0) {
    c = b;
    a += 1;
}
return a;
}
function bnBitLength() {
if (this.t <= 0) return 0;
return this.DB * (this.t - 1) + nbits(this[this.t - 1] ^ (this.s & this.DM));
}
function bnpDLShiftTo(b, c) {
var a;
for (a = this.t - 1; a >= 0; --a) c[a + b] = this[a];
for (a = b - 1; a >= 0; --a) c[a] = 0;
c.t = this.t + b;
c.s = this.s;
}
function bnpDRShiftTo(b, c) {
for (var a = b; a < this.t; ++a) c[a - b] = this[a];
c.t = Math.max(this.t - b, 0);
c.s = this.s;
}
function bnpLShiftTo(h, j) {
var b = h % this.DB;
var e = this.DB - b;
var a = (1 << e) - 1;
var f = Math.floor(h / this.DB),
d = (this.s << b) & this.DM,
g;
for (g = this.t - 1; g >= 0; --g) {
    j[g + f + 1] = (this[g] >> e) | d;
    d = (this[g] & a) << b;
}
for (g = f - 1; g >= 0; --g) j[g] = 0;
j[f] = d;
j.t = this.t + f + 1;
j.s = this.s;
j.clamp();
}
function bnpRShiftTo(f, g) {
g.s = this.s;
var d = Math.floor(f / this.DB);
if (d >= this.t) {
    g.t = 0;
    return;
}
var b = f % this.DB;
var c = this.DB - b;
var a = (1 << b) - 1;
g[0] = this[d] >> b;
for (var e = d + 1; e < this.t; ++e) {
    g[e - d - 1] |= (this[e] & a) << c;
    g[e - d] = this[e] >> b;
}
if (b > 0) g[this.t - d - 1] |= (this.s & a) << c;
g.t = this.t - d;
g.clamp();
}
function bnpSubTo(b, g) {
var e = 0,
d = 0,
f = Math.min(b.t, this.t);
while (e < f) {
    d += this[e] - b[e];
    g[e++] = d & this.DM;
    d >>= this.DB;
}
if (b.t < this.t) {
    d -= b.s;
    while (e < this.t) {
        d += this[e];
        g[e++] = d & this.DM;
        d >>= this.DB;
    }
    d += this.s;
} else {
    d += this.s;
    while (e < b.t) {
        d -= b[e];
        g[e++] = d & this.DM;
        d >>= this.DB;
    }
    d -= b.s;
}
g.s = (d < 0) ? -1 : 0;
if (d < -1) g[e++] = this.DV + d;
else if (d > 0) g[e++] = d;
g.t = e;
g.clamp();
}
function bnpMultiplyTo(b, d) {
var e = this.abs(),
f = b.abs();
var c = e.t;
d.t = c + f.t;
while (--c >= 0) d[c] = 0;
for (c = 0; c < f.t; ++c) d[c + e.t] = e.am(0, f[c], d, c, 0, e.t);
d.s = 0;
d.clamp();
if (this.s != b.s) BigInteger.ZERO.subTo(d, d);
}
function bnpSquareTo(d) {
var e = this.abs();
var b = d.t = 2 * e.t;
while (--b >= 0) d[b] = 0;
for (b = 0; b < e.t - 1; ++b) {
    var a = e.am(b, e[b], d, 2 * b, 0, 1);
    if ((d[b + e.t] += e.am(b + 1, 2 * e[b], d, 2 * b + 1, a, e.t - b - 1)) >= e.DV) {
        d[b + e.t] -= e.DV;
        d[b + e.t + 1] = 1;
    }
}
if (d.t > 0) d[d.t - 1] += e.am(b, e[b], d, 2 * b, 0, 1);
d.s = 0;
d.clamp();
}
function bnpDivRemTo(g, o, s) {
var l = g.abs();
if (l.t <= 0) return;
var n = this.abs();
if (n.t < l.t) {
    if (o != null) o.fromInt(0);
    if (s != null) this.copyTo(s);
    return;
}
if (s == null) s = nbi();
var x = nbi(),
w = this.s,
h = g.s;
var k = this.DB - nbits(l[l.t - 1]);
if (k > 0) {
    l.lShiftTo(k, x);
    n.lShiftTo(k, s);
} else {
    l.copyTo(x);
    n.copyTo(s);
}
var B = x.t;
var A = x[B - 1];
if (A == 0) return;
var C = A * (1 << this.F1) + ((B > 1) ? x[B - 2] >> this.F2: 0);
var a = this.FV / C,
b = (1 << this.F1) / C,
c = 1 << this.F2;
var d = s.t,
f = d - B,
u = (o == null) ? nbi() : o;
x.dlShiftTo(f, u);
if (s.compareTo(u) >= 0) {
    s[s.t++] = 1;
    s.subTo(u, s);
}
BigInteger.ONE.dlShiftTo(B, u);
u.subTo(x, x);
while (x.t < B) x[x.t++] = 0;
while (--f >= 0) {
    var p = (s[--d] == A) ? this.DM: Math.floor(s[d] * a + (s[d - 1] + c) * b);
    if ((s[d] += x.am(0, p, s, f, 0, B)) < p) {
        x.dlShiftTo(f, u);
        s.subTo(u, s);
        while (s[d] < --p) s.subTo(u, s);
    }
}
if (o != null) {
    s.drShiftTo(B, o);
    if (w != h) BigInteger.ZERO.subTo(o, o);
}
s.t = B;
s.clamp();
if (k > 0) s.rShiftTo(k, s);
if (w < 0) BigInteger.ZERO.subTo(s, s);
}
function bnMod(b) {
var c = nbi();
this.abs().divRemTo(b, null, c);
if (this.s < 0 && c.compareTo(BigInteger.ZERO) > 0) b.subTo(c, c);
return c;
}
function Classic(a) {
this.m = a;
}
function cConvert(a) {
if (a.s < 0 || a.compareTo(this.m) >= 0) return a.mod(this.m);
else return a;
}
function cRevert(a) {
return a;
}
function cReduce(a) {
a.divRemTo(this.m, null, a);
}
function cMulTo(b, c, a) {
b.multiplyTo(c, a);
this.reduce(a);
}
function cSqrTo(b, a) {
b.squareTo(a);
this.reduce(a);
}
Classic.prototype.convert = cConvert;
Classic.prototype.revert = cRevert;
Classic.prototype.reduce = cReduce;
Classic.prototype.mulTo = cMulTo;
Classic.prototype.sqrTo = cSqrTo;
function bnpInvDigit() {
if (this.t < 1) return 0;
var a = this[0];
if ((a & 1) == 0) return 0;
var b = a & 3;
b = (b * (2 - (a & 0xf) * b)) & 0xf;
b = (b * (2 - (a & 0xff) * b)) & 0xff;
b = (b * (2 - (((a & 0xffff) * b) & 0xffff))) & 0xffff;
b = (b * (2 - a * b % this.DV)) % this.DV;
return (b > 0) ? this.DV - b: -b;
}
function Montgomery(a) {
this.m = a;
this.mp = a.invDigit();
this.mpl = this.mp & 0x7fff;
this.mph = this.mp >> 15;
this.um = (1 << (a.DB - 15)) - 1;
this.mt2 = 2 * a.t;
}
function montConvert(b) {
var a = nbi();
b.abs().dlShiftTo(this.m.t, a);
a.divRemTo(this.m, null, a);
if (b.s < 0 && a.compareTo(BigInteger.ZERO) > 0) this.m.subTo(a, a);
return a;
}
function montRevert(b) {
var a = nbi();
b.copyTo(a);
this.reduce(a);
return a;
}
function montReduce(d) {
while (d.t <= this.mt2) d[d.t++] = 0;
for (var a = 0; a < this.m.t; ++a) {
    var b = d[a] & 0x7fff;
    var c = (b * this.mpl + (((b * this.mph + (d[a] >> 15) * this.mpl) & this.um) << 15)) & d.DM;
    b = a + this.m.t;
    d[b] += this.m.am(0, c, d, a, 0, this.m.t);
    while (d[b] >= d.DV) {
        d[b] -= d.DV;
        d[++b]++;
    }
}
d.clamp();
d.drShiftTo(this.m.t, d);
if (d.compareTo(this.m) >= 0) d.subTo(this.m, d);
}
function montSqrTo(b, a) {
b.squareTo(a);
this.reduce(a);
}
function montMulTo(b, c, a) {
b.multiplyTo(c, a);
this.reduce(a);
}
Montgomery.prototype.convert = montConvert;
Montgomery.prototype.revert = montRevert;
Montgomery.prototype.reduce = montReduce;
Montgomery.prototype.mulTo = montMulTo;
Montgomery.prototype.sqrTo = montSqrTo;
function bnpIsEven() {
return ((this.t > 0) ? (this[0] & 1) : this.s) == 0;
}
function bnpExp(a, j) {
if (a > 0xffffffff || a < 1) return BigInteger.ONE;
var d = nbi(),
f = nbi(),
b = j.convert(this),
c = nbits(a) - 1;
b.copyTo(d);
while (--c >= 0) {
    j.sqrTo(d, f);
    if ((a & (1 << c)) > 0) j.mulTo(f, b, d);
    else {
        var h = d;
        d = f;
        f = h;
    }
}
return j.revert(d);
}
function bnModPowInt(a, b) {
var c;
if (a < 256 || b.isEven()) c = new Classic(b);
else c = new Montgomery(b);
return this.exp(a, c);
}
BigInteger.prototype.copyTo = bnpCopyTo;
BigInteger.prototype.fromInt = bnpFromInt;
BigInteger.prototype.fromString = bnpFromString;
BigInteger.prototype.clamp = bnpClamp;
BigInteger.prototype.dlShiftTo = bnpDLShiftTo;
BigInteger.prototype.drShiftTo = bnpDRShiftTo;
BigInteger.prototype.lShiftTo = bnpLShiftTo;
BigInteger.prototype.rShiftTo = bnpRShiftTo;
BigInteger.prototype.subTo = bnpSubTo;
BigInteger.prototype.multiplyTo = bnpMultiplyTo;
BigInteger.prototype.squareTo = bnpSquareTo;
BigInteger.prototype.divRemTo = bnpDivRemTo;
BigInteger.prototype.invDigit = bnpInvDigit;
BigInteger.prototype.isEven = bnpIsEven;
BigInteger.prototype.exp = bnpExp;
BigInteger.prototype.toString = bnToString;
BigInteger.prototype.negate = bnNegate;
BigInteger.prototype.abs = bnAbs;
BigInteger.prototype.compareTo = bnCompareTo;
BigInteger.prototype.bitLength = bnBitLength;
BigInteger.prototype.mod = bnMod;
BigInteger.prototype.modPowInt = bnModPowInt;
BigInteger.ZERO = nbv(0);
BigInteger.ONE = nbv(1);
function Arcfour() {
this.i = 0;
this.j = 0;
this.S = new Array();
}
function ARC4init(c) {
var a, b, d;
for (a = 0; a < 256; ++a) this.S[a] = a;
b = 0;
for (a = 0; a < 256; ++a) {
    b = (b + this.S[a] + c[a % c.length]) & 255;
    d = this.S[a];
    this.S[a] = this.S[b];
    this.S[b] = d;
}
this.i = 0;
this.j = 0;
}
function ARC4next() {
var a;
this.i = (this.i + 1) & 255;
this.j = (this.j + this.S[this.i]) & 255;
a = this.S[