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))&255;if(p<=0){p+=this.DB;--i}}if((d&128)!=0){d|=-256}if(k==0&&(this.s&128)!=(d&128)){++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&65535)==0){x>>=16;r+=16}if((x&255)==0){x>>=8;r+=8}if((x&15)==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 bnSquare(){var r=nbi();this.squareTo(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){if(n==0){return}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,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997];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[Math.floor(Math.random()*lowprimes.length)]);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;BigInteger.prototype.square=bnSquare;