/*
  Developed by Alexander Wilhelm and Tom Wu.

  Commercial License.
*/
function bnClone(){var r=nbi();this.copyTo(r);return r;}
function bnIntValue(){
if(this.s<0){
if(this.t==1)return this[0]-this.DV;
else if(this.t==0)return-1;
}
else if(this.t==1)return this[0];
else if(this.t==0)return 0;
return((this[1]&((1<<(32-this.DB))-1))<<this.DB)|this[0];
}
function bnByteValue(){return(this.t==0)?this.s:(this[0]<<24)>>24;}
function bnShortValue(){return(this.t==0)?this.s:(this[0]<<16)>>16;}
function bnpChunkSize(r){return Math.floor(Math.LN2*this.DB/Math.log(r));}
function bnSigNum(){
if(this.s<0)return-1;
else if(this.t<=0||(this.t==1&&this[0]<=0))return 0;
else return 1;
}
function bnpToRadix(b){
if(b==null)b=10;
if(this.signum()==0||b<2||b>36)return"0";
var cs=this.chunkSize(b);
var a=Math.pow(b,cs);
var d=nbv(a),y=nbi(),z=nbi(),r="";
this.divRemTo(d,y,z);
while(y.signum()>0){
r=(a+z.intValue()).toString(b).substr(1)+r;
y.divRemTo(d,y,z);
}
return z.intValue().toString(b)+r;
}
function bnpFromRadix(s,b){
this.fromInt(0);
if(b==null)b=10;
var cs=this.chunkSize(b);
var d=Math.pow(b,cs),mi=false,j=0,w=0;
for(var i=0;i<s.length;++i){
var x=intAt(s,i);
if(x<0){
if(s.charAt(i)=="-"&&this.signum()==0)mi=true;
continue;
}
w=b*w+x;
if(++j>=cs){
this.dMultiply(d);
this.dAddOffset(w,0);
j=0;
w=0;
}
}
if(j>0){
this.dMultiply(Math.pow(b,j));
this.dAddOffset(w,0);
}
if(mi)BigInteger.ZERO.subTo(this,this);
}
function bnpFromNumber(a,b,c){
if("number"==typeof b){
if(a<2)this.fromInt(1);
else{
this.fromNumber(a,c);
if(!this.testBit(a-1))
this.bitwiseTo(BigInteger.ONE.shiftLeft(a-1),op_or,this);
if(this.isEven())this.dAddOffset(1,0);
while(!this.isProbablePrime(b)){
this.dAddOffset(2,0);
if(this.bitLength()>a)this.subTo(BigInteger.ONE.shiftLeft(a-1),this);
}
}
}
else{
var x=new Array(),t=a&7;
x.length=(a>>3)+1;
b.nextBytes(x);
if(t>0)x[0]&=((1<<t)-1);else x[0]=0;
this.fromString(x,256);
}
}
function bnToByteArray(){
var i=this.t,r=new Array();
r[0]=this.s;
var p=this.DB-(i*this.DB)%8,d,k=0;
if(i-->0){
if(p<this.DB&&(d=this[i]>>p)!=(this.s&this.DM)>>p)
r[k++]=d|(this.s<<(this.DB-p));
while(i>=0){
if(p<8){
d=(this[i]&((1<<p)-1))<<(8-p);
d|=this[--i]>>(p+=this.DB-8);
}
else{
d=(this[i]>>(p-=8))&0xff;
if(p<=0){p+=this.DB;--i;}
}
if((d&0x80)!=0)d|=-256;
if(k==0&&(this.s&0x80)!=(d&0x80))++k;
if(k>0||d!=this.s)r[k++]=d;
}
}
return r;
}
function bnEquals(a){return(this.compareTo(a)==0);}
function bnMin(a){return(this.compareTo(a)<0)?this:a;}
function bnMax(a){return(this.compareTo(a)>0)?this:a;}
function bnpBitwiseTo(a,op,r){
var i,f,m=Math.min(a.t,this.t);
for(i=0;i<m;++i)r[i]=op(this[i],a[i]);
if(a.t<this.t){
f=a.s&this.DM;
for(i=m;i<this.t;++i)r[i]=op(this[i],f);
r.t=this.t;
}
else{
f=this.s&this.DM;
for(i=m;i<a.t;++i)r[i]=op(f,a[i]);
r.t=a.t;
}
r.s=op(this.s,a.s);
r.clamp();
}
function op_and(x,y){return x&y;}
function bnAnd(a){var r=nbi();this.bitwiseTo(a,op_and,r);return r;}
function op_or(x,y){return x|y;}
function bnOr(a){var r=nbi();this.bitwiseTo(a,op_or,r);return r;}
function op_xor(x,y){return x^y;}
function bnXor(a){var r=nbi();this.bitwiseTo(a,op_xor,r);return r;}
function op_andnot(x,y){return x&~y;}
function bnAndNot(a){var r=nbi();this.bitwiseTo(a,op_andnot,r);return r;}
function bnNot(){
var r=nbi();
for(var i=0;i<this.t;++i)r[i]=this.DM&~this[i];
r.t=this.t;
r.s=~this.s;
return r;
}
function bnShiftLeft(n){
var r=nbi();
if(n<0)this.rShiftTo(-n,r);else this.lShiftTo(n,r);
return r;
}
function bnShiftRight(n){
var r=nbi();
if(n<0)this.lShiftTo(-n,r);else this.rShiftTo(n,r);
return r;
}
function lbit(x){
if(x==0)return-1;
var r=0;
if((x&0xffff)==0){x>>=16;r+=16;}
if((x&0xff)==0){x>>=8;r+=8;}
if((x&0xf)==0){x>>=4;r+=4;}
if((x&3)==0){x>>=2;r+=2;}
if((x&1)==0)++r;
return r;
}
function bnGetLowestSetBit(){
for(var i=0;i<this.t;++i)
if(this[i]!=0)return i*this.DB+lbit(this[i]);
if(this.s<0)return this.t*this.DB;
return-1;
}
function cbit(x){
var r=0;
while(x!=0){x&=x-1;++r;}
return r;
}
function bnBitCount(){
var r=0,x=this.s&this.DM;
for(var i=0;i<this.t;++i)r+=cbit(this[i]^x);
return r;
}
function bnTestBit(n){
var j=Math.floor(n/this.DB);
if(j>=this.t)return(this.s!=0);
return((this[j]&(1<<(n%this.DB)))!=0);
}
function bnpChangeBit(n,op){
var r=BigInteger.ONE.shiftLeft(n);
this.bitwiseTo(r,op,r);
return r;
}
function bnSetBit(n){return this.changeBit(n,op_or);}
function bnClearBit(n){return this.changeBit(n,op_andnot);}
function bnFlipBit(n){return this.changeBit(n,op_xor);}
function bnpAddTo(a,r){
var i=0,c=0,m=Math.min(a.t,this.t);
while(i<m){
c+=this[i]+a[i];
r[i++]=c&this.DM;
c>>=this.DB;
}
if(a.t<this.t){
c+=a.s;
while(i<this.t){
c+=this[i];
r[i++]=c&this.DM;
c>>=this.DB;
}
c+=this.s;
}
else{
c+=this.s;
while(i<a.t){
c+=a[i];
r[i++]=c&this.DM;
c>>=this.DB;
}
c+=a.s;
}
r.s=(c<0)?-1:0;
if(c>0)r[i++]=c;
else if(c<-1)r[i++]=this.DV+c;
r.t=i;
r.clamp();
}
function bnAdd(a){var r=nbi();this.addTo(a,r);return r;}
function bnSubtract(a){var r=nbi();this.subTo(a,r);return r;}
function bnMultiply(a){var r=nbi();this.multiplyTo(a,r);return r;}
function bnDivide(a){var r=nbi();this.divRemTo(a,r,null);return r;}
function bnRemainder(a){var r=nbi();this.divRemTo(a,null,r);return r;}
function bnDivideAndRemainder(a){
var q=nbi(),r=nbi();
this.divRemTo(a,q,r);
return new Array(q,r);
}
function bnpDMultiply(n){
this[this.t]=this.am(0,n-1,this,0,0,this.t);
++this.t;
this.clamp();
}
function bnpDAddOffset(n,w){
while(this.t<=w)this[this.t++]=0;
this[w]+=n;
while(this[w]>=this.DV){
this[w]-=this.DV;
if(++w>=this.t)this[this.t++]=0;
++this[w];
}
}
function NullExp(){}
function nNop(x){return x;}
function nMulTo(x,y,r){x.multiplyTo(y,r);}
function nSqrTo(x,r){x.squareTo(r);}
NullExp.prototype.convert=nNop;
NullExp.prototype.revert=nNop;
NullExp.prototype.mulTo=nMulTo;
NullExp.prototype.sqrTo=nSqrTo;
function bnPow(e){return this.exp(e,new NullExp());}
function bnpMultiplyLowerTo(a,n,r){
var i=Math.min(this.t+a.t,n);
r.s=0;
r.t=i;
while(i>0)r[--i]=0;
var j;
for(j=r.t-this.t;i<j;++i)r[i+this.t]=this.am(0,a[i],r,i,0,this.t);
for(j=Math.min(a.t,n);i<j;++i)this.am(0,a[i],r,i,0,n-i);
r.clamp();
}
function bnpMultiplyUpperTo(a,n,r){
--n;
var i=r.t=this.t+a.t-n;
r.s=0;
while(--i>=0)r[i]=0;
for(i=Math.max(n-this.t,0);i<a.t;++i)
r[this.t+i-n]=this.am(n-i,a[i],r,0,0,this.t+i-n);
r.clamp();
r.drShiftTo(1,r);
}
function Barrett(m){
this.r2=nbi();
this.q3=nbi();
BigInteger.ONE.dlShiftTo(2*m.t,this.r2);
this.mu=this.r2.divide(m);
this.m=m;
}
function barrettConvert(x){
if(x.s<0||x.t>2*this.m.t)return x.mod(this.m);
else if(x.compareTo(this.m)<0)return x;
else{var r=nbi();x.copyTo(r);this.reduce(r);return r;}
}
function barrettRevert(x){return x;}
function barrettReduce(x){
x.drShiftTo(this.m.t-1,this.r2);
if(x.t>this.m.t+1){x.t=this.m.t+1;x.clamp();}
this.mu.multiplyUpperTo(this.r2,this.m.t+1,this.q3);
this.m.multiplyLowerTo(this.q3,this.m.t+1,this.r2);
while(x.compareTo(this.r2)<0)x.dAddOffset(1,this.m.t+1);
x.subTo(this.r2,x);
while(x.compareTo(this.m)>=0)x.subTo(this.m,x);
}
function barrettSqrTo(x,r){x.squareTo(r);this.reduce(r);}
function barrettMulTo(x,y,r){x.multiplyTo(y,r);this.reduce(r);}
Barrett.prototype.convert=barrettConvert;
Barrett.prototype.revert=barrettRevert;
Barrett.prototype.reduce=barrettReduce;
Barrett.prototype.mulTo=barrettMulTo;
Barrett.prototype.sqrTo=barrettSqrTo;
function bnModPow(e,m){
var i=e.bitLength(),k,r=nbv(1),z;
if(i<=0)return r;
else if(i<18)k=1;
else if(i<48)k=3;
else if(i<144)k=4;
else if(i<768)k=5;
else k=6;
if(i<8)
z=new Classic(m);
else if(m.isEven())
z=new Barrett(m);
else
z=new Montgomery(m);
var g=new Array(),n=3,k1=k-1,km=(1<<k)-1;
g[1]=z.convert(this);
if(k>1){
var g2=nbi();
z.sqrTo(g[1],g2);
while(n<=km){
g[n]=nbi();
z.mulTo(g2,g[n-2],g[n]);
n+=2;
}
}
var j=e.t-1,w,is1=true,r2=nbi(),t;
i=nbits(e[j])-1;
while(j>=0){
if(i>=k1)w=(e[j]>>(i-k1))&km;
else{
w=(e[j]&((1<<(i+1))-1))<<(k1-i);
if(j>0)w|=e[j-1]>>(this.DB+i-k1);
}
n=k;
while((w&1)==0){w>>=1;--n;}
if((i-=n)<0){i+=this.DB;--j;}
if(is1){
g[w].copyTo(r);
is1=false;
}
else{
while(n>1){z.sqrTo(r,r2);z.sqrTo(r2,r);n-=2;}
if(n>0)z.sqrTo(r,r2);else{t=r;r=r2;r2=t;}
z.mulTo(r2,g[w],r);
}
while(j>=0&&(e[j]&(1<<i))==0){
z.sqrTo(r,r2);t=r;r=r2;r2=t;
if(--i<0){i=this.DB-1;--j;}
}
}
return z.revert(r);
}
function bnGCD(a){
var x=(this.s<0)?this.negate():this.clone();
var y=(a.s<0)?a.negate():a.clone();
if(x.compareTo(y)<0){var t=x;x=y;y=t;}
var i=x.getLowestSetBit(),g=y.getLowestSetBit();
if(g<0)return x;
if(i<g)g=i;
if(g>0){
x.rShiftTo(g,x);
y.rShiftTo(g,y);
}
while(x.signum()>0){
if((i=x.getLowestSetBit())>0)x.rShiftTo(i,x);
if((i=y.getLowestSetBit())>0)y.rShiftTo(i,y);
if(x.compareTo(y)>=0){
x.subTo(y,x);
x.rShiftTo(1,x);
}
else{
y.subTo(x,y);
y.rShiftTo(1,y);
}
}
if(g>0)y.lShiftTo(g,y);
return y;
}
function bnpModInt(n){
if(n<=0)return 0;
var d=this.DV%n,r=(this.s<0)?n-1:0;
if(this.t>0)
if(d==0)r=this[0]%n;
else for(var i=this.t-1;i>=0;--i)r=(d*r+this[i])%n;
return r;
}
function bnModInverse(m){
var ac=m.isEven();
if((this.isEven()&&ac)||m.signum()==0)return BigInteger.ZERO;
var u=m.clone(),v=this.clone();
var a=nbv(1),b=nbv(0),c=nbv(0),d=nbv(1);
while(u.signum()!=0){
while(u.isEven()){
u.rShiftTo(1,u);
if(ac){
if(!a.isEven()||!b.isEven()){a.addTo(this,a);b.subTo(m,b);}
a.rShiftTo(1,a);
}
else if(!b.isEven())b.subTo(m,b);
b.rShiftTo(1,b);
}
while(v.isEven()){
v.rShiftTo(1,v);
if(ac){
if(!c.isEven()||!d.isEven()){c.addTo(this,c);d.subTo(m,d);}
c.rShiftTo(1,c);
}
else if(!d.isEven())d.subTo(m,d);
d.rShiftTo(1,d);
}
if(u.compareTo(v)>=0){
u.subTo(v,u);
if(ac)a.subTo(c,a);
b.subTo(d,b);
}
else{
v.subTo(u,v);
if(ac)c.subTo(a,c);
d.subTo(b,d);
}
}
if(v.compareTo(BigInteger.ONE)!=0)return BigInteger.ZERO;
if(d.compareTo(m)>=0)return d.subtract(m);
if(d.signum()<0)d.addTo(m,d);else return d;
if(d.signum()<0)return d.add(m);else return d;
}
var lowprimes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509];
var lplim=(1<<26)/lowprimes[lowprimes.length-1];
function bnIsProbablePrime(t){
var i,x=this.abs();
if(x.t==1&&x[0]<=lowprimes[lowprimes.length-1]){
for(i=0;i<lowprimes.length;++i)
if(x[0]==lowprimes[i])return true;
return false;
}
if(x.isEven())return false;
i=1;
while(i<lowprimes.length){
var m=lowprimes[i],j=i+1;
while(j<lowprimes.length&&m<lplim)m*=lowprimes[j++];
m=x.modInt(m);
while(i<j)if(m%lowprimes[i++]==0)return false;
}
return x.millerRabin(t);
}
function bnpMillerRabin(t){
var n1=this.subtract(BigInteger.ONE);
var k=n1.getLowestSetBit();
if(k<=0)return false;
var r=n1.shiftRight(k);
t=(t+1)>>1;
if(t>lowprimes.length)t=lowprimes.length;
var a=nbi();
for(var i=0;i<t;++i){
a.fromInt(lowprimes[i]);
var y=a.modPow(r,this);
if(y.compareTo(BigInteger.ONE)!=0&&y.compareTo(n1)!=0){
var j=1;
while(j++<k&&y.compareTo(n1)!=0){
y=y.modPowInt(2,this);
if(y.compareTo(BigInteger.ONE)==0)return false;
}
if(y.compareTo(n1)!=0)return false;
}
}
return true;
}
BigInteger.prototype.chunkSize=bnpChunkSize;
BigInteger.prototype.toRadix=bnpToRadix;
BigInteger.prototype.fromRadix=bnpFromRadix;
BigInteger.prototype.fromNumber=bnpFromNumber;
BigInteger.prototype.bitwiseTo=bnpBitwiseTo;
BigInteger.prototype.changeBit=bnpChangeBit;
BigInteger.prototype.addTo=bnpAddTo;
BigInteger.prototype.dMultiply=bnpDMultiply;
BigInteger.prototype.dAddOffset=bnpDAddOffset;
BigInteger.prototype.multiplyLowerTo=bnpMultiplyLowerTo;
BigInteger.prototype.multiplyUpperTo=bnpMultiplyUpperTo;
BigInteger.prototype.modInt=bnpModInt;
BigInteger.prototype.millerRabin=bnpMillerRabin;
BigInteger.prototype.clone=bnClone;
BigInteger.prototype.intValue=bnIntValue;
BigInteger.prototype.byteValue=bnByteValue;
BigInteger.prototype.shortValue=bnShortValue;
BigInteger.prototype.signum=bnSigNum;
BigInteger.prototype.toByteArray=bnToByteArray;
BigInteger.prototype.equals=bnEquals;
BigInteger.prototype.min=bnMin;
BigInteger.prototype.max=bnMax;
BigInteger.prototype.and=bnAnd;
BigInteger.prototype.or=bnOr;
BigInteger.prototype.xor=bnXor;
BigInteger.prototype.andNot=bnAndNot;
BigInteger.prototype.not=bnNot;
BigInteger.prototype.shiftLeft=bnShiftLeft;
BigInteger.prototype.shiftRight=bnShiftRight;
BigInteger.prototype.getLowestSetBit=bnGetLowestSetBit;
BigInteger.prototype.bitCount=bnBitCount;
BigInteger.prototype.testBit=bnTestBit;
BigInteger.prototype.setBit=bnSetBit;
BigInteger.prototype.clearBit=bnClearBit;
BigInteger.prototype.flipBit=bnFlipBit;
BigInteger.prototype.add=bnAdd;
BigInteger.prototype.subtract=bnSubtract;
BigInteger.prototype.multiply=bnMultiply;
BigInteger.prototype.divide=bnDivide;
BigInteger.prototype.remainder=bnRemainder;
BigInteger.prototype.divideAndRemainder=bnDivideAndRemainder;
BigInteger.prototype.modPow=bnModPow;
BigInteger.prototype.modInverse=bnModInverse;
BigInteger.prototype.pow=bnPow;
BigInteger.prototype.gcd=bnGCD;
BigInteger.prototype.isProbablePrime=bnIsProbablePrime;