#1176142 (Java) No.3620 Compositional Power with Schröder Coordinate 2

• 問題: No.3620 Compositional Power with Schröder Coordinate 2
• ユーザー: 37zigen
• 提出日時: 2026-08-11 04:28:49
• 言語: Java (openjdk 25.0.2)
• 結果: AC
• 実行時間: 1,759 ms / 10,000 ms
• コード長: 31,842 bytes
• コンパイル時間: 3,190 ms
• コンパイル使用メモリ: 115,276 KB
• 実行使用メモリ: 184,788 KB
• 最終ジャッジ日時: 2026-08-11 04:29:07
• 合計ジャッジ時間: 14,363 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 7

ソースコード

import java.io.IOException;import java.io.InputStream;import java.io.OutputStream;import java.io.PrintStream;import java.io.PrintWriter;import java.lang.reflect.Array;import java.math.BigInteger;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Collection;import java.util.Collections;import java.util.Comparator;import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;import java.util.List;import java.util.Map.Entry;import java.util.Map;import java.util.NoSuchElementException;import java.util.Objects;import java.util.Queue;import java.util.Random;import java.util.Set;import java.util.TreeMap;import java.util.function.BiFunction;import java.util.function.DoubleUnaryOperator;import java.util.function.IntBinaryOperator;import java.util.function.IntFunction;import java.util.function.IntToDoubleFunction;import java.util.function.IntToLongFunction;import java.util.function.IntUnaryOperator;import java.util.function.LongBinaryOperator;import java.util.function.LongToDoubleFunction;import java.util.function.LongUnaryOperator;import java.util.function.Predicate;import java.util.function.ToIntFunction;import java.util.random.RandomGenerator;import java.util.stream.IntStream;import java.util.stream.LongStream;import java.util.stream.Stream;public class Main{static MyPrintWriter pw=MyPrintWriter.getInstance();static FastScanner sc=FastScanner.getInstance();public static void main(String[]args)throws IOException{Thread.setDefaultUncaughtExceptionHandler((t,e)->System.exit(1));new Main().run();pw.flush();}void run(){int N=sc.nextInt();int M=sc.nextInt();long[]A=sc.nextLongs(N);long[]B=sc.nextLongs(N);long[]C=sc.nextLongs(N);Fp fp=Fp.MOD998244353;var mod=fp.modulus();long A1=A[1];var P=PolynomialFpDynamic.MOD998244353;var powG=P.powerProjectionWithKnownInverse(C,N-1);var dot=new long[N];for(int i=0;(i<C.length)&&(i<powG.length);i++){dot[i]=(C[i]*powG[i])%mod;}var eval=P.evaluateAtGeometricProgression(dot,A1,M);pw.println(eval);}}class ArrayUtils{public static void swap(int i,int j,long[]A){if(i==j){return;}long tmp=A[i];A[i]=A[j];A[j]=tmp;}public static void swap(long[]A,long[]B){if(A.length!=B.length){throw new AssertionError();}for(int i=0;i<A.length;i++){long tmp=A[i];A[i]=B[i];B[i]=tmp;}}public static void reverse(long[]a){int s=0;int t=a.length-1;while(s<t){swap(s,t,a);++s;--t;}}}interface CommutativeRingStrategy<T>extends RingStrategy<T>{}interface EuclideanDomainStrategy<T>extends GCDDomainStrategy<T>{T div(T a,T b);T mod(T a,T b);long norm(T a);default T canonicalUnit(T a){return one();}@Override default T gcd(T a,T b){while(!equals(b,zero())){a=mod(a,b);T t=a;a=b;b=t;}if(equals(a,zero())){return a;}return div(a,canonicalUnit(a));}record ExtGCDResult<T>(T x,T y,T gcd){}default ExtGCDResult<T>extgcd(T a,T b){T x0=one();T y0=zero();T g0=a;T x1=zero();T y1=one();T g1=b;while(!equals(g1,zero())){T q=div(g0,g1);T nextG=sub(g0,mul(q,g1));T nextX=sub(x0,mul(q,x1));T nextY=sub(y0,mul(q,y1));x0=x1;y0=y1;g0=g1;x1=nextX;y1=nextY;g1=nextG;}if(equals(g0,zero())){return new ExtGCDResult<>(x0,y0,g0);}T u=canonicalUnit(g0);return new ExtGCDResult<>(div(x0,u),div(y0,u),div(g0,u));}}interface ExactDivRingStrategy<T>extends IntegralDomainStrategy<T>{T exactDiv(T a,T b);}class FastScanner{private static FastScanner instance=null;private final InputStream in=System.in;private final byte[]buffer=new byte[1<<16];private int ptr=0;private int buflen=0;private FastScanner(){}public static FastScanner getInstance(){if(instance==null){instance=new FastScanner();}return instance;}private boolean hasNextByte(){if(ptr<buflen){return true;}ptr=0;try{buflen=in.read(buffer);}catch(IOException e){e.printStackTrace();}return buflen>0;}private int readByte(){if(hasNextByte()){return buffer[ptr++];}else{return-1;}}private boolean isPrintableChar(int c){return(33<=c)&&(c<=126);}public boolean hasNext(){while(hasNextByte()&&(!isPrintableChar(buffer[ptr]))){ptr++;}return hasNextByte();}public long nextLong(){if(!hasNext()){throw new NoSuchElementException();}long n=0;boolean minus=false;int b=readByte();if(b=='-'){minus=true;b=readByte();}while((b>='0')&&(b<='9')){n=((n<<1)+(n<<3))+(b-'0');b=readByte();}return minus?-n:n;}public int nextInt(){return((int)(nextLong()));}public long[]nextLongs(int n){long[]a=new long[n];for(int i=0;i<n;++i){a[i]=nextLong();}return a;}}class Fp extends Zn implements LongFieldStrategy{public static final Fp MOD998244353=new Fp(998244353);public Fp(long mod){super(mod);}int[]inv=new int[0];public long inv(long n){if(n<0){n=reduce(n);}return n<inv.length?inv[((int)(n))]&0xffffffffL:MathUtils.modInv(n,mod);}@Override public long div(long a,long b){return mul(a,inv(b));}@Override public long mod(long a,long b){if(equals(b,zero())){throw new ArithmeticException("Division by zero");}return zero();}@Override public long norm(long a){return equals(a,zero())?0:1;}@Override public long canonicalUnit(long a){if(equals(a,zero())){return one();}return a;}public long pow(long a,long n){if(n<0){a=inv(a);n=-n;}return MathUtils.modPow(a,n,mod);}}interface GCDDomainStrategy<T>extends IntegralDomainStrategy<T>{T gcd(T a,T b);}interface IntegralDomainStrategy<T>extends CommutativeRingStrategy<T>{}interface LongCommutativeRingStrategy extends LongRingStrategy{}interface LongEuclideanDomainStrategy extends LongGCDDomainStrategy{long div(long a,long b);long mod(long a,long b);long norm(long a);default long canonicalUnit(long a){return one();}@Override default long gcd(long a,long b){while(!equals(b,zero())){a=mod(a,b);long t=a;a=b;b=t;}if(equals(a,zero())){return a;}return div(a,canonicalUnit(a));}record ExtGCDResult(long x,long y,long gcd){}default ExtGCDResult extgcd(long a,long b){long x0=one();long y0=zero();long g0=a;long x1=zero();long y1=one();long g1=b;while(!equals(g1,zero())){long q=div(g0,g1);long nextG=sub(g0,mul(q,g1));long nextX=sub(x0,mul(q,x1));long nextY=sub(y0,mul(q,y1));x0=x1;y0=y1;g0=g1;x1=nextX;y1=nextY;g1=nextG;}if(equals(g0,zero())){return new ExtGCDResult(x0,y0,g0);}long u=canonicalUnit(g0);return new ExtGCDResult(div(x0,u),div(y0,u),div(g0,u));}}interface LongExactDivRingStrategy extends LongIntegralDomainStrategy{long divExact(long a,long b);}interface LongFieldStrategy extends LongEuclideanDomainStrategy,LongExactDivRingStrategy{@Override default long divExact(long a,long b){return div(a,b);}long inv(long a);default long div(long a,long b){return mul(a,inv(b));}default long geometricSum(long a){return inv(sub(one(),a));}@Override default ExtGCDResult extgcd(long a,long b){if(!equals(a,zero())){return new ExtGCDResult(inv(a),zero(),one());}else if(!equals(b,zero())){return new ExtGCDResult(zero(),inv(b),one());}else{return new ExtGCDResult(zero(),zero(),zero());}}}interface LongGCDDomainStrategy extends LongIntegralDomainStrategy{long gcd(long a,long b);}interface LongIntegralDomainStrategy extends LongCommutativeRingStrategy{}interface LongRingStrategy extends LongSemiRingStrategy{long neg(long a);default long sub(long a,long b){return add(a,neg(b));}}interface LongSemiRingStrategy{long zero();long one();long add(long a,long b);long mul(long a,long b);boolean equals(long a,long b);}class MathUtils{public static long modPow(long a,long n,long mod){if(n<0){long inv=MathUtils.modInv(a,mod);return MathUtils.modPow(inv,-n,mod);}if(n==0){return 1;}return(MathUtils.modPow((a*a)%mod,n/2,mod)*((n%2)==1?a:1))%mod;}public static long modInv(long a,long mod){a=((a%mod)+mod)%mod;long[]f0=new long[]{1,0,mod};long[]f1=new long[]{0,1,a};while(f1[2]!=0){long q=f0[2]/f1[2];for(int i=0;i<3;i++){f0[i]-=q*f1[i];}ArrayUtils.swap(f0,f1);}return f0[1]<0?mod+f0[1]:f0[1];}}class MyPrintWriter extends PrintWriter{private static MyPrintWriter instance=null;private MyPrintWriter(){super(System.out);}public static MyPrintWriter getInstance(){if(instance==null){instance=new MyPrintWriter();}return instance;}public void println(long[]a){println(a," ");}public void println(long[]a,String separator){for(int i=0;i<a.length;++i){super.print(a[i]+(i==(a.length-1)?"":separator));}super.println();}}class PolynomialFpDynamic extends PolynomialZnDynamic implements EuclideanDomainStrategy<long[]>,UFDStrategy<long[]>,ExactDivRingStrategy<long[]>{Fp fp;public final boolean isNTTFriendly;public final long primitiveRoot;public final int maxPow2;long[][]bitreversedRoots;long[][]bitreversedInvRoots;public static final int FFT_NAIVE_THRESHOLD=128;public static final int FFT_MIN_LENGTH_THRESHOLD=10;public static final PolynomialFpDynamic MOD998244353=new PolynomialFpDynamic(998244353L,3);public static final PolynomialFpDynamic MOD469762049=new PolynomialFpDynamic(469762049L,3);public static final PolynomialFpDynamic MOD167772161=new PolynomialFpDynamic(167772161L,3);public PolynomialFpDynamic(long mod,long primitiveRoot){super(mod);fp=new Fp(mod);this.isNTTFriendly=true;this.primitiveRoot=primitiveRoot;this.maxPow2=Long.numberOfTrailingZeros(mod-1);this.bitreversedRoots=new long[maxPow2+1][];this.bitreversedInvRoots=new long[maxPow2+1][];}void prepareRoots(int n){if(Integer.bitCount(n)!=1){throw new AssertionError();}int sz=Integer.numberOfTrailingZeros(n);if(sz>maxPow2){throw new AssertionError("NTT length exceeds mod - 1 power of two");}if(bitreversedRoots[sz]!=null){return;}long root=MathUtils.modPow(primitiveRoot,(mod-1)/n,mod);long iroot=MathUtils.modInv(root,mod);bitreversedRoots[sz]=new long[n];bitreversedInvRoots[sz]=new long[n];for(int n_=n/2;n_>=1;n_/=2,root=(root*root)%mod,iroot=(iroot*iroot)%mod){long w=1;long iw=1;for(int j=0;j<n_;++j){bitreversedRoots[sz][n_+j]=w;bitreversedInvRoots[sz][n_+j]=iw;w=(w*root)%mod;iw=(iw*iroot)%mod;}int cur=0;for(int j=0;j<n_;++j){if(cur<j){ArrayUtils.swap(n_+cur,n_+j,bitreversedRoots[sz]);ArrayUtils.swap(n_+cur,n_+j,bitreversedInvRoots[sz]);}for(int k=n_/2;k>(cur^=k);k/=2);}}}public void fftToBitReversed(long[]a){int n=a.length;int sz=Integer.numberOfTrailingZeros(n);prepareRoots(n);for(int m=1,t=n/2;m<=(n/2);m*=2,t/=2){for(int i=0,k=0;i<m;++i,k+=2*t){long s=bitreversedRoots[sz][m+i];for(int j=k;j<(k+t);++j){long u=a[j];long v=(a[j+t]*s)%mod;a[j]=addMod(u,v);a[j+t]=subMod(u,v);}}}}public void ifftFromBitReversed(long[]a){long invN=MathUtils.modInv(a.length,mod);int n=a.length;int sz=Integer.numberOfTrailingZeros(n);prepareRoots(n);for(int m=n/2,t=1;m>=1;m/=2,t*=2){for(int i=0,k=0;i<m;++i,k+=2*t){long s=bitreversedInvRoots[sz][m+i];if(m==1){s=(s*invN)%mod;}for(int j=k;j<(k+t);++j){long u=a[j];long v=a[j+t];if(m==1){a[j]=((u+v)*invN)%mod;}else{a[j]=addMod(u,v);}a[j+t]=(((u+mod)-v)*s)%mod;}}}}public long[]mulFFT(long[]a,long[]b){if((a.length==0)||(b.length==0)){return new long[0];}int n=1;int len=(a.length+b.length)-1;while(n<len){n*=2;}if(Integer.numberOfTrailingZeros(n)>maxPow2){throw new AssertionError("NTT length exceeds mod - 1 power of two");}long[]fa=new long[n];long[]fb=new long[n];for(int i=0;i<a.length;i++){fa[i]=fp.reduce(a[i]);}for(int i=0;i<b.length;i++){fb[i]=fp.reduce(b[i]);}prepareRoots(n);fftToBitReversed(fa);fftToBitReversed(fb);for(int i=0;i<n;++i){fa[i]=(fa[i]*fb[i])%mod;}ifftFromBitReversed(fa);return Arrays.copyOf(fa,len);}@Override public long[]mul(long[]a,long[]b){if((a.length==0)||(b.length==0)){return new long[0];}if((a.length==1)&&(b.length==1)){return new long[]{(a[0]*b[0])%mod};}int n=a.length;int m=b.length;if((isNTTFriendly&&(((n+m)-1)>FFT_NAIVE_THRESHOLD))&&(Math.min(n,m)>FFT_MIN_LENGTH_THRESHOLD)){return mulFFT(a,b);}return super.mul(a,b);}@Override public long[]squared(long[]a){if(a.length==0){return new long[0];}if(a.length==1){return new long[]{(a[0]*a[0])%mod};}int len=(2*a.length)-1;if(isNTTFriendly&&(len>FFT_NAIVE_THRESHOLD)){return squaredFFT(a);}return super.squared(a);}private long[]squaredFFT(long[]a){if(a.length==0){return new long[0];}int n=1;int len=(2*a.length)-1;while(n<len){n*=2;}if(Integer.numberOfTrailingZeros(n)>maxPow2){throw new AssertionError("NTT length exceeds mod - 1 power of two");}long[]fa=new long[n];for(int i=0;i<a.length;i++){fa[i]=fp.reduce(a[i]);}prepareRoots(n);fftToBitReversed(fa);for(int i=0;i<n;++i){fa[i]=(fa[i]*fa[i])%mod;}ifftFromBitReversed(fa);return Arrays.copyOf(fa,len);}@Override public long[]powFull(long[]a,int n){if(n==0){return new long[]{1};}if(n==1){return a.clone();}int d=deg(a);if(d==(-1)){return new long[0];}if(d==0){return new long[]{MathUtils.modPow(a[0],n,mod)};}if(d<=40){return sparsePow(a,(d*n)+1,n);}long[]ret=new long[1];ret[0]=1;long[]b=a.clone();while(n!=0){if((n%2)==1){ret=mul(ret,b);}n/=2;if(n==0){break;}b=mul(b,b);}return ret;}@Override public boolean equals(Object o){if(this==o){return true;}if((o==null)||(getClass()!=o.getClass())){return false;}PolynomialFpDynamic that=((PolynomialFpDynamic)(o));return mod==that.mod;}@Override public int hashCode(){return Objects.hash(mod);}public long[]monic(long[]a){int deg=deg(a);if(deg==(-1)){return new long[0];}if(deg==0){return new long[]{1};}long inv=fp.inv(a[deg]);long[]res=new long[deg+1];for(int i=0;i<deg;i++){res[i]=(a[i]*inv)%mod;}res[deg]=1;return res;}public long[]divNaive(long[]a,long[]b){int degA=deg(a);int degB=deg(b);if(degB==(-1)){throw new ArithmeticException("division by zero polynomial");}if(degA<degB){return new long[]{0};}long[]r=Arrays.copyOf(a,degA+1);long[]q=new long[(degA-degB)+1];long invB=fp.inv(b[degB]);for(int i=degA;i>=degB;i--){if(r[i]==0){continue;}long c=(r[i]*invB)%mod;q[i-degB]=c;for(int j=0;j<=degB;j++){r[(i-degB)+j]-=(c*b[j])%mod;if(r[(i-degB)+j]<0){r[(i-degB)+j]+=mod;}}}return resize(q);}public long[]modNaive(long[]a,long[]b){int degA=deg(a);int degB=deg(b);if(degB==(-1)){throw new ArithmeticException("division by zero polynomial");}if(degA<degB){return resize(a);}long[]r=Arrays.copyOf(a,degA+1);long invB=fp.inv(b[degB]);for(int i=degA;i>=degB;i--){if(r[i]==0){continue;}long c=(r[i]*invB)%mod;for(int j=0;j<=degB;j++){r[(i-degB)+j]-=(c*b[j])%mod;if(r[(i-degB)+j]<0){r[(i-degB)+j]+=mod;}}}return resize(r);}public static class DivModResult{public long[]q;public long[]r;public DivModResult(long[]q,long[]r){this.q=q;this.r=r;}}public DivModResult divmod(long[]a,long[]b){var q=div(a,b);var r=sub(a,mul(q,b));r=resize(r);return new DivModResult(q,r);}public long[]gcdNaive(long[]a,long[]b){a=resize(a);b=resize(b);while(deg(b)!=(-1)){long[]r=modNaive(a,b);a=b;b=r;}return monic(a);}public long[]differentiate(long[]a){long[]ret=new long[a.length];for(int i=1;i<a.length;++i){ret[i-1]=(i*a[i])%mod;}return ret;}public long[]integrate(long[]a){long[]ret=new long[a.length];for(int i=0;(i+1)<a.length;++i){ret[i+1]=(MathUtils.modInv(i+1,mod)*a[i])%mod;}return ret;}public long[]invNaive(long[]a){long[]g=new long[a.length];long inv0=MathUtils.modInv(a[0],mod);g[0]=inv0;for(int i=1;i<a.length;i++){long sum=0;for(int j=1;j<=i;j++){if(j<a.length){sum=(sum+(a[j]*g[i-j]))%mod;}}g[i]=(sum==0)?0:(((mod-sum)%mod)*inv0)%mod;}return g;}public long[]invFFT(long[]a){long[]g=new long[]{MathUtils.modInv(a[0],mod)};for(int len=1;len<a.length;len*=2){long[]fftG=Arrays.copyOf(g,len*4);long[]fftA=new long[4*len];System.arraycopy(a,0,fftA,0,Math.min(2*len,a.length));prepareRoots(4*len);fftToBitReversed(fftG);fftToBitReversed(fftA);for(int i=0;i<fftG.length;++i){fftG[i]=(((fftG[i]*fftG[i])%mod)*fftA[i])%mod;}ifftFromBitReversed(fftG);for(int i=0;i<len;++i){fftG[i]=g[i];}for(int i=len;i<(2*len);++i){if(fftG[i]!=0){fftG[i]=mod-fftG[i];}}g=Arrays.copyOf(fftG,Math.min(a.length,2*len));}return g;}public long[]inv(long[]a){if(a[0]==0){throw new AssertionError();}return isNTTFriendly?invFFT(a):invNaive(a);}public long[]log(long[]a){return integrate(Arrays.copyOf(mul(differentiate(a),inv(a)),a.length));}public long[]expNaive(long[]a){if(a[0]!=0){throw new AssertionError();}int n=a.length;long[]g=new long[n];long[]df=new long[n];for(int i=0;i<n;i++){df[i]=(i*a[i])%mod;}g[0]=1;for(int i=1;i<n;i++){long sum=0;for(int j=1;j<=i;j++){sum=(sum+(df[j]*g[i-j]))%mod;}g[i]=(sum*fp.inv(i))%mod;}return g;}public long[]expFFT(long[]a){if(a[0]!=0){throw new AssertionError();}long[]g=new long[]{1};for(int len=1;len<a.length;len*=2){long[]tmp=sub(Arrays.copyOf(a,Math.min(2*len,a.length)),log(Arrays.copyOf(g,Math.min(2*len,a.length))));tmp[0]=addMod(tmp[0],1);g=Arrays.copyOf(mul(g,tmp),Math.min(2*len,a.length));}return Arrays.copyOf(g,a.length);}public long[]exp(long[]a){return isNTTFriendly?expFFT(a):expNaive(a);}public long[]mul(long[]a,long b){long[]ret=new long[a.length];for(int i=0;i<a.length;i++){ret[i]=(a[i]*b)%mod;}return ret;}public long[]pow(long[]a,long m){int len=a.length;if(m==0){long[]ret=new long[len];ret[0]=1;return ret;}if(m==1){return a.clone();}if(m==2){return squared(a);}int s=0;while((s<a.length)&&(a[s]==0)){++s;}if(s==a.length){return a.clone();}long[]aa=(s!=0)?Arrays.copyOfRange(a,s,a.length):a.clone();long b=MathUtils.modInv(aa[0],mod);for(int i=0;i<aa.length;i++){aa[i]=(b*aa[i])%mod;}aa=log(aa);for(int i=0;i<aa.length;i++){aa[i]=((m%mod)*aa[i])%mod;}aa=exp(aa);b=MathUtils.modPow(MathUtils.modInv(b,mod),m%(mod-1),mod);for(int i=0;i<aa.length;i++){aa[i]=(b*aa[i])%mod;}long[]ret=new long[len];if(s<=((len-1)/m)){for(long i=((long)(s))*m;(i<len)&&((i-(s*m))<aa.length);++i){ret[((int)(i))]=aa[((int)(i-(s*m)))];}}return ret;}@Override public long[]exactDiv(long[]a,long[]b){return div(a,b);}@Override public long[]div(long[]a,long[]b){if(b.length==1){if(b[0]==0){throw new ArithmeticException("Division by zero");}if(b[0]==1){return a.clone();}long inv=fp.inv(b[0]);long[]res=new long[a.length];for(int i=0;i<a.length;i++){res[i]=(a[i]*inv)%mod;}return res;}int degA=deg(a);int degB=deg(b);if((isNTTFriendly&&(((degA-degB)+1)>FFT_NAIVE_THRESHOLD))&&(degB>=10)){return divFast(a,b);}return divNaive(a,b);}public long[]divFast(long[]a,long[]b){int degA=deg(a);int degB=deg(b);if(degA<degB){return new long[]{0};}long[]ra=resize(a);long[]rb=resize(b);ArrayUtils.reverse(ra);ArrayUtils.reverse(rb);rb=Arrays.copyOf(rb,degA+1);long[]q=mul(ra,inv(rb));q=Arrays.copyOf(q,(degA-degB)+1);ArrayUtils.reverse(q);return q;}@Override public long[]mod(long[]a,long[]b){int degA=deg(a);int degB=deg(b);if(isNTTFriendly&&(((degA-degB)+1)>FFT_NAIVE_THRESHOLD)){return modFast(a,b);}return modNaive(a,b);}public long[]modFast(long[]a,long[]b){long[]q=divFast(a,b);return resize(sub(a,mul(b,q)));}public class HalfGcdResult{public long[]p00;public long[]p01;public long[]p10;public long[]p11;public HalfGcdResult(long[]p00,long[]p01,long[]p10,long[]p11){this.p00=p00;this.p01=p01;this.p10=p10;this.p11=p11;}public long[][]apply(long[]a,long[]b){return new long[][]{resize(add(mul(p00,a),mul(p01,b))),resize(add(mul(p10,a),mul(p11,b)))};}HalfGcdResult swapColumns(){return new HalfGcdResult(p01,p00,p11,p10);}}HalfGcdResult identityMatrix(){return new HalfGcdResult(new long[]{1},new long[]{0},new long[]{0},new long[]{1});}HalfGcdResult leftMulEuclideanStep(HalfGcdResult mat,long[]q){return new HalfGcdResult(mat.p10,mat.p11,sub(mat.p00,mul(q,mat.p10)),sub(mat.p01,mul(q,mat.p11)));}HalfGcdResult multiplyMatrix(HalfGcdResult a,HalfGcdResult b){return new HalfGcdResult(resize(add(mul(a.p00,b.p00),mul(a.p01,b.p10))),resize(add(mul(a.p00,b.p01),mul(a.p01,b.p11))),resize(add(mul(a.p10,b.p00),mul(a.p11,b.p10))),resize(add(mul(a.p10,b.p01),mul(a.p11,b.p11))));}HalfGcdResult halfGcdNaiveOrdered(long[]a,long[]b){int threshold=deg(a)/2;HalfGcdResult mat=identityMatrix();while(deg(b)>threshold){DivModResult dm=divmod(a,b);mat=leftMulEuclideanStep(mat,dm.q);a=b;b=dm.r;}return mat;}public HalfGcdResult halfGcd(long[]a,long[]b){a=resize(a);b=resize(b);int degA=deg(a);int degB=deg(b);if(degB==(-1)){return identityMatrix();}if(degA<degB){return halfGcd(b,a).swapColumns();}if(degB<=(degA/2)){return identityMatrix();}if(degA<=128){return halfGcdNaiveOrdered(a,b);}int threshold=degA/2;int shift=(degA+1)/2;HalfGcdResult mat=halfGcd(divideByX(a,shift),divideByX(b,shift));long[][]cd=mat.apply(a,b);long[]c=cd[0];long[]d=cd[1];if(deg(d)<=threshold){return mat;}DivModResult dm=divmod(c,d);mat=leftMulEuclideanStep(mat,dm.q);c=d;d=dm.r;if(deg(d)<=threshold){return mat;}int secondShift=(2*threshold)-deg(c);if(secondShift<0){throw new AssertionError();}return multiplyMatrix(halfGcd(divideByX(c,secondShift),divideByX(d,secondShift)),mat);}@Override public long[]gcd(long[]a,long[]b){int degA=deg(a);int degB=deg(b);if(degA==(-1)){return monic(b);}if(degB==(-1)){return monic(a);}if((degA==0)||(degB==0)){return new long[]{1};}a=resize(a);b=resize(b);if(degA<degB){long[]t=a;a=b;b=t;}while(deg(b)!=(-1)){if((!isNTTFriendly)||(Math.max(deg(a),deg(b))<=3072)){return gcdNaive(a,b);}HalfGcdResult mat=halfGcd(a,b);long[][]cd=mat.apply(a,b);a=cd[0];b=cd[1];if(deg(b)==(-1)){break;}DivModResult dm=divmod(a,b);a=b;b=dm.r;if(deg(a)<deg(b)){long[]t=a;a=b;b=t;}}return monic(a);}@Override public EuclideanDomainStrategy.ExtGCDResult<long[]>extgcd(long[]f,long[]g){f=resize(f);g=resize(g);long[]a=f;long[]b=g;long[]x0=new long[]{1};long[]y0=new long[]{0};long[]x1=new long[]{0};long[]y1=new long[]{1};if(Math.max(deg(a),deg(b))<=3072){while(deg(b)!=(-1)){DivModResult dm=divmod(a,b);long[]nx=sub(x0,mul(dm.q,x1));long[]ny=sub(y0,mul(dm.q,y1));a=b;b=dm.r;x0=x1;y0=y1;x1=resize(nx);y1=resize(ny);}}else{if(deg(a)<deg(b)){long[]t=a;a=b;b=t;t=x0;x0=x1;x1=t;t=y0;y0=y1;y1=t;}while(deg(b)!=(-1)){HalfGcdResult mat=halfGcd(a,b);long[][]cd=mat.apply(a,b);long[]nx0=resize(add(mul(mat.p00,x0),mul(mat.p01,x1)));long[]ny0=resize(add(mul(mat.p00,y0),mul(mat.p01,y1)));long[]nx1=resize(add(mul(mat.p10,x0),mul(mat.p11,x1)));long[]ny1=resize(add(mul(mat.p10,y0),mul(mat.p11,y1)));a=cd[0];b=cd[1];x0=nx0;y0=ny0;x1=nx1;y1=ny1;if(deg(b)==(-1)){break;}DivModResult dm=divmod(a,b);nx1=resize(sub(x0,mul(dm.q,x1)));ny1=resize(sub(y0,mul(dm.q,y1)));a=b;b=dm.r;x0=x1;y0=y1;x1=nx1;y1=ny1;if(deg(a)<deg(b)){long[]t=a;a=b;b=t;t=x0;x0=x1;x1=t;t=y0;y0=y1;y1=t;}}}a=resize(a);int d=deg(a);if(d==(-1)){return new EuclideanDomainStrategy.ExtGCDResult<>(new long[]{0},new long[]{0},new long[]{0});}long inv=MathUtils.modInv(a[d],mod);return new EuclideanDomainStrategy.ExtGCDResult<>(resize(mul(x0,inv)),resize(mul(y0,inv)),resize(mul(a,inv)));}public long[]evaluateAtGeometricProgression(long[]coeffs,long c,int m){if((coeffs.length==0)||(m==0)){return new long[0];}int n=coeffs.length;if(c==0){long[]result=new long[m];for(int i=0;i<coeffs.length;i++){result[0]+=coeffs[i];result[0]%=mod;}for(int i=1;i<result.length;i++){result[i]=fp.reduce(coeffs[0]);}return result;}if(c==1){long sum=0;for(long v:coeffs){sum=addMod(sum,fp.reduce(v));}long[]result=new long[m];Arrays.fill(result,sum);return result;}int maxIdx=(n+m)-2;long[]cPowT=new long[maxIdx+1];long[]cInvPowT=new long[maxIdx+1];long cInv=MathUtils.modInv(c,mod);cPowT[0]=1;cInvPowT[0]=1;long cPowI=1;long cInvPowI=1;for(int i=1;i<=maxIdx;i++){cPowT[i]=(cPowT[i-1]*cPowI)%mod;cInvPowT[i]=(cInvPowT[i-1]*cInvPowI)%mod;cPowI=(cPowI*c)%mod;cInvPowI=(cInvPowI*cInv)%mod;}long[]A=new long[n];for(int i=0;i<n;i++){long y_i=(fp.reduce(coeffs[i])*cInvPowT[i])%mod;A[(n-1)-i]=y_i;}int vLen=(n+m)-1;long[]V=new long[vLen];for(int j=0;j<vLen;j++){V[j]=cPowT[j];}long[]conv=mul(A,V);long[]result=new long[m];for(int k=0;k<m;k++){result[k]=(conv[(n-1)+k]*cInvPowT[k])%mod;}return result;}public long[]powerProjectionWithKnownInverse(long[]h,long[]gh,int N,int K){if(N<0){return new long[K];}long[]res=new long[K];if(N==0){if(K>0){res[0]=gh[0];}return res;}if(h.length<(N+1)){throw new AssertionError();}long[]ht=Arrays.copyOf(h,N+1);long[]hp=differentiate(ht);long[]hDivW=new long[N+1];for(int i=0;i<N;i++){hDivW[i]=h[i+1];}long[]wDivH=inv(hDivW);long[]wDivHPow=pow(wDivH,N+1);long[]P=mul(gh,hp);P=Arrays.copyOf(P,N+1);P=mul(P,wDivHPow);P=Arrays.copyOf(P,N+1);for(int m=0;(m<K)&&(m<=N);m++){res[m]=P[N-m];}return res;}public long[]powerProjectionWithKnownInverse(long[]h,int N){return powerProjectionWithKnownInverse(h,new long[]{1},N,N+1);}public long[]sparsePow(long[]f,int n,long k){if(n<=0){return new long[0];}if(k==0){long[]res=new long[n];res[0]=1;return res;}int d0=0;while(((d0<f.length)&&(d0<n))&&(fp.reduce(f[d0])==0)){d0++;}if((d0==f.length)||(d0>=n)){return new long[n];}if((d0>0)&&(((n-1)/d0)<k)){return new long[n];}int bias=((int)(d0*k));if(bias>=n){return new long[n];}ArrayList<PolynomialZnDynamic.Term>terms=new ArrayList<>();for(int i=d0+1;(i<f.length)&&(i<n);i++){long v=fp.reduce(f[i]);if(v!=0){terms.add(new PolynomialZnDynamic.Term(i-d0,v));}}long[]res=new long[n];long f0=fp.reduce(f[d0]);res[bias]=MathUtils.modPow(f0,k%(mod-1),mod);long inv0=fp.inv(f0);long kMod=k%mod;for(int d=0;((bias+d)+1)<n;d++){long tmp=0;for(PolynomialZnDynamic.Term t:terms){int j=d-t.d;if(j>=0){tmp=((tmp+mod)-((((t.v*res[(bias+j)+1])%mod)*(j+1))%mod))%mod;}j=d-(t.d-1);if(j>=0){tmp=(tmp+((((((t.v*t.d)%mod)*res[bias+j])%mod)*kMod)%mod))%mod;}}res[(bias+d)+1]=(((tmp*inv0)%mod)*fp.inv(d+1))%mod;}return res;}}class PolynomialZnDynamic implements CommutativeRingStrategy<long[]>{public final long mod;public final Zn zn;public PolynomialZnDynamic(long mod){this.mod=mod;this.zn=new Zn(mod);}protected long addMod(long a,long b){long sum=a+b;return sum>=mod?sum-mod:sum;}protected long subMod(long a,long b){long diff=a-b;return diff<0?diff+mod:diff;}public int countTerms(long[]a,int limit){int count=0;for(long v:a){if(zn.reduce(v)!=0){count++;if(count>limit){return count;}}}return count;}public long[]mulNaive(long[]a,long[]b){long[]c=new long[(a.length+b.length)-1];for(int i=0;i<a.length;i++){if(a[i]==0){continue;}for(int j=0;j<b.length;j++){if(b[j]==0){continue;}c[i+j]=(c[i+j]+(a[i]*b[j]))%mod;}}return c;}protected long[]mulCRT(long[]a,long[]b){int n=a.length;int m=b.length;long m1=998244353L;long m2=469762049L;long m3=167772161L;double maxVal=(((double)(Math.min(n,m)))*(mod-1))*(mod-1);int k_count=3;if(maxVal<m1){k_count=1;}else if(maxVal<(((double)(m1))*m2)){k_count=2;}long[]res1=PolynomialFpDynamic.MOD998244353.mulFFT(a,b);if(k_count==1){for(int i=0;i<res1.length;i++){res1[i]%=mod;}return res1;}long[]res2=PolynomialFpDynamic.MOD469762049.mulFFT(a,b);if(k_count==2){int len=res1.length;long[]res=new long[len];long[]v=new long[2];long[]ms=new long[]{m1,m2};for(int i=0;i<len;i++){v[0]=res1[i];v[1]=res2[i];res[i]=Zn.crt(v,ms)%mod;}return res;}long[]res3=PolynomialFpDynamic.MOD167772161.mulFFT(a,b);int len=res1.length;long[]res=new long[len];long inv123=MathUtils.modInv(((m1%m3)*(m2%m3))%m3,m3);long m12m=((m1%mod)*(m2%mod))%mod;long[]v=new long[2];long[]ms=new long[]{m1,m2};for(int i=0;i<len;i++){v[0]=res1[i];v[1]=res2[i];long x12=Zn.crt(v,ms);long k3=((((res3[i]-(x12%m3))+m3)%m3)*inv123)%m3;res[i]=((x12%mod)+(((k3%mod)*m12m)%mod))%mod;}return res;}@Override public long[]mul(long[]a,long[]b){if((a.length==0)||(b.length==0)){return new long[0];}if((a.length==1)&&(b.length==1)){return new long[]{(a[0]*b[0])%mod};}int n=a.length;int m=b.length;if(((n+m)-1)<=128){return mulNaive(a,b);}int sparseThreshold=50;int countB=countTerms(b,sparseThreshold);if(countB<=sparseThreshold){return sparseMul(a,getTerms(b,countB),b.length);}int countA=countTerms(a,sparseThreshold);if(countA<=sparseThreshold){return sparseMul(b,getTerms(a,countA),a.length);}if(((n+m)-1)>128){return mulCRT(a,b);}return mulNaive(a,b);}public long[]squared(long[]a){if(a.length==0){return new long[0];}if(a.length==1){return new long[]{(a[0]*a[0])%mod};}int len=(2*a.length)-1;if(len>128){return mulCRT(a,a);}return squaredNaive(a);}public long[]squaredNaive(long[]a){int len=(2*a.length)-1;long[]ret=new long[len];for(int i=0;i<a.length;++i){if(a[i]==0){continue;}for(int j=i+1;j<a.length;++j){if(a[j]==0){continue;}ret[i+j]=(ret[i+j]+((2*a[i])*a[j]))%mod;}}for(int i=0;i<a.length;++i){if(a[i]==0){continue;}ret[2*i]=(ret[2*i]+(a[i]*a[i]))%mod;}return ret;}public long[]powFull(long[]a,int n){if(n==0){return new long[]{1};}if(n==1){return a.clone();}int d=deg(a);if(d==(-1)){return new long[0];}if(d==0){return new long[]{MathUtils.modPow(a[0],n,mod)};}long[]ret=new long[1];ret[0]=1;long[]b=a.clone();while(n!=0){if((n%2)==1){ret=mul(ret,b);}n/=2;if(n==0){break;}b=mul(b,b);}return ret;}@Override public long[]zero(){return new long[0];}@Override public long[]one(){return new long[]{1};}@Override public long[]add(long[]a,long[]b){long[]ret=new long[Math.max(a.length,b.length)];for(int i=0;i<ret.length;++i){ret[i]=(i<a.length?a[i]:0)+(i<b.length?b[i]:0);if(ret[i]>=mod){ret[i]-=mod;}}return ret;}@Override public long[]neg(long[]a){long[]ret=new long[a.length];for(int i=0;i<a.length;i++){if(a[i]!=0){ret[i]=mod-a[i];}}return ret;}@Override public boolean equals(long[]a,long[]b){int n=Math.max(a.length,b.length);for(int i=0;i<n;i++){long va=(i<a.length)?a[i]:0;long vb=(i<b.length)?b[i]:0;if(va!=vb){return false;}}return true;}@Override public boolean equals(Object o){if(this==o){return true;}if((o==null)||(getClass()!=o.getClass())){return false;}PolynomialZnDynamic that=((PolynomialZnDynamic)(o));return mod==that.mod;}@Override public int hashCode(){return Objects.hash(mod);}public long norm(long[]a){return deg(a)+1;}public long[]canonicalUnit(long[]a){int d=deg(a);if(d==(-1)){return one();}return new long[]{a[d]};}@Override public long[]sub(long[]a,long[]b){if((a.length==1)&&(b.length==1)){long diff=a[0]-b[0];if(diff<0){diff+=mod;}return new long[]{diff};}long[]ret=new long[Math.max(a.length,b.length)];for(int i=0;i<ret.length;++i){ret[i]=(i<a.length?a[i]:0)-(i<b.length?b[i]:0);if(ret[i]<0){ret[i]+=mod;}}return ret;}public int deg(long[]a){int n=a.length;if(n==0){return-1;}if(a[n-1]!=0){return n-1;}for(int i=n-2;i>=0;i--){if(a[i]!=0){return i;}}return-1;}public boolean isZero(long[]f){return deg(f)==(-1);}public long[]resize(long[]a){return Arrays.copyOf(a,Math.max(0,deg(a))+1);}public static class Term{public final int d;public final long v;public Term(int d,long v){this.d=d;this.v=v;}}public long[]sparseMul(long[]a,ArrayList<Term>sparseTerms,int sparseLen){if((a.length==0)||(sparseLen==0)){return new long[0];}long[]res=new long[(a.length+sparseLen)-1];if(sparseTerms.isEmpty()){return res;}for(int i=0;i<a.length;i++){long v=zn.reduce(a[i]);if(v==0){continue;}for(Term t:sparseTerms){res[i+t.d]=(res[i+t.d]+(v*t.v))%mod;}}return res;}public ArrayList<Term>getTerms(long[]p,int initialCapacity){ArrayList<Term>terms=new ArrayList<>(initialCapacity);for(int i=0;i<p.length;i++){long v=zn.reduce(p[i]);if(v!=0){terms.add(new Term(i,v));}}return terms;}public long[]divideByX(long[]f,int repeat){return Arrays.copyOfRange(f,repeat,f.length);}}interface RingStrategy<T>extends SemiRingStrategy<T>{T neg(T a);default T sub(T a,T b){return add(a,neg(b));}}interface SemiRingStrategy<T>{T zero();T one();T add(T a,T b);T mul(T a,T b);boolean equals(T a,T b);default T pow(T a,long n){if(n<0){throw new IllegalArgumentException("Exponent must be non-negative");}T res=one();T base=a;while(n>0){if((n&1)==1){res=mul(res,base);}base=mul(base,base);n>>=1;}return res;}default boolean isZero(T a){return equals(zero(),a);}default boolean isOne(T a){return equals(one(),a);}default int hashCode(T a){return Objects.hashCode(a);}}interface UFDStrategy<T>extends GCDDomainStrategy<T>{}class Zn implements LongCommutativeRingStrategy{final long mod;public Zn(long mod){this.mod=mod;}public long modulus(){return this.mod;}@Override public long zero(){return 0;}@Override public long one(){return 1%mod;}public long pow(long a,long n){if(n<0){throw new AssertionError();}return MathUtils.modPow(a,n,mod);}public static long crt(long[]a,long[]m){int N=a.length;long fac=1;long x=0;for(int i=0;i<N;i++){Fp mo=new Fp(m[i]);long c=mo.reduce((a[i]%m[i])-(x%m[i]))*MathUtils.modInv(fac%m[i],m[i]);c=mo.reduce(c);x=x+(fac*c);fac*=m[i];}return x;}@Override public long add(long a,long b){long ret=(a+b)%mod;if(ret<0){ret+=mod;}return ret;}public long sub(long a,long b){long ret=(a-b)%mod;if(ret<0){ret+=mod;}return ret;}@Override public long mul(long a,long b){return(a*b)%mod;}@Override public long neg(long a){return a==0?0:mod-a;}@Override public boolean equals(long a,long b){return a==b;}public long reduce(long a){a%=mod;if(a<0){a+=mod;}return a;}}