#define PROBLEM \
"http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_2_F"
#include"../../math/bigint.hpp"//intmain(){biginta,b;cin>>a>>b;cout<<a*b<<endl;}
#line 1 "verify/verify-aoj-ntl/aoj-ntl-2-f.test.cpp"
#define PROBLEM \
"http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_2_F"
#line 2 "math/bigint.hpp"
#include<algorithm>
#include<cassert>
#include<cmath>
#include<iostream>
#include<tuple>
#include<utility>
#include<vector>usingnamespacestd;#line 2 "internal/internal-type-traits.hpp"
#include<type_traits>usingnamespacestd;namespaceinternal{template<typenameT>usingis_broadly_integral=typenameconditional_t<is_integral_v<T>||is_same_v<T,__int128_t>||is_same_v<T,__uint128_t>,true_type,false_type>::type;template<typenameT>usingis_broadly_signed=typenameconditional_t<is_signed_v<T>||is_same_v<T,__int128_t>,true_type,false_type>::type;template<typenameT>usingis_broadly_unsigned=typenameconditional_t<is_unsigned_v<T>||is_same_v<T,__uint128_t>,true_type,false_type>::type;#define ENABLE_VALUE(x) \
template <typename T> \
constexpr bool x##_v = x<T>::value;
ENABLE_VALUE(is_broadly_integral);ENABLE_VALUE(is_broadly_signed);ENABLE_VALUE(is_broadly_unsigned);#undef ENABLE_VALUE
#define ENABLE_HAS_TYPE(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<typename T::var>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
#define ENABLE_HAS_VAR(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
}// namespace internal#line 2 "ntt/arbitrary-ntt.hpp"
#line 2 "modint/montgomery-modint.hpp"
template<uint32_tmod>structLazyMontgomeryModInt{usingmint=LazyMontgomeryModInt;usingi32=int32_t;usingu32=uint32_t;usingu64=uint64_t;staticconstexpru32get_r(){u32ret=mod;for(i32i=0;i<4;++i)ret*=2-mod*ret;returnret;}staticconstexpru32r=get_r();staticconstexpru32n2=-u64(mod)%mod;static_assert(mod<(1<<30),"invalid, mod >= 2 ^ 30");static_assert((mod&1)==1,"invalid, mod % 2 == 0");static_assert(r*mod==1,"this code has bugs.");u32a;constexprLazyMontgomeryModInt():a(0){}constexprLazyMontgomeryModInt(constint64_t&b):a(reduce(u64(b%mod+mod)*n2)){};staticconstexpru32reduce(constu64&b){return(b+u64(u32(b)*u32(-r))*mod)>>32;}constexprmint&operator+=(constmint&b){if(i32(a+=b.a-2*mod)<0)a+=2*mod;return*this;}constexprmint&operator-=(constmint&b){if(i32(a-=b.a)<0)a+=2*mod;return*this;}constexprmint&operator*=(constmint&b){a=reduce(u64(a)*b.a);return*this;}constexprmint&operator/=(constmint&b){*this*=b.inverse();return*this;}constexprmintoperator+(constmint&b)const{returnmint(*this)+=b;}constexprmintoperator-(constmint&b)const{returnmint(*this)-=b;}constexprmintoperator*(constmint&b)const{returnmint(*this)*=b;}constexprmintoperator/(constmint&b)const{returnmint(*this)/=b;}constexprbooloperator==(constmint&b)const{return(a>=mod?a-mod:a)==(b.a>=mod?b.a-mod:b.a);}constexprbooloperator!=(constmint&b)const{return(a>=mod?a-mod:a)!=(b.a>=mod?b.a-mod:b.a);}constexprmintoperator-()const{returnmint()-mint(*this);}constexprmintoperator+()const{returnmint(*this);}constexprmintpow(u64n)const{mintret(1),mul(*this);while(n>0){if(n&1)ret*=mul;mul*=mul;n>>=1;}returnret;}constexprmintinverse()const{intx=get(),y=mod,u=1,v=0,t=0,tmp=0;while(y>0){t=x/y;x-=t*y,u-=t*v;tmp=x,x=y,y=tmp;tmp=u,u=v,v=tmp;}returnmint{u};}friendostream&operator<<(ostream&os,constmint&b){returnos<<b.get();}friendistream&operator>>(istream&is,mint&b){int64_tt;is>>t;b=LazyMontgomeryModInt<mod>(t);return(is);}constexpru32get()const{u32ret=reduce(a);returnret>=mod?ret-mod:ret;}staticconstexpru32get_mod(){returnmod;}};#line 2 "ntt/ntt.hpp"
template<typenamemint>structNTT{staticconstexpruint32_tget_pr(){uint32_t_mod=mint::get_mod();usingu64=uint64_t;u64ds[32]={};intidx=0;u64m=_mod-1;for(u64i=2;i*i<=m;++i){if(m%i==0){ds[idx++]=i;while(m%i==0)m/=i;}}if(m!=1)ds[idx++]=m;uint32_t_pr=2;while(1){intflg=1;for(inti=0;i<idx;++i){u64a=_pr,b=(_mod-1)/ds[i],r=1;while(b){if(b&1)r=r*a%_mod;a=a*a%_mod;b>>=1;}if(r==1){flg=0;break;}}if(flg==1)break;++_pr;}return_pr;};staticconstexpruint32_tmod=mint::get_mod();staticconstexpruint32_tpr=get_pr();staticconstexprintlevel=__builtin_ctzll(mod-1);mintdw[level],dy[level];voidsetwy(intk){mintw[level],y[level];w[k-1]=mint(pr).pow((mod-1)/(1<<k));y[k-1]=w[k-1].inverse();for(inti=k-2;i>0;--i)w[i]=w[i+1]*w[i+1],y[i]=y[i+1]*y[i+1];dw[1]=w[1],dy[1]=y[1],dw[2]=w[2],dy[2]=y[2];for(inti=3;i<k;++i){dw[i]=dw[i-1]*y[i-2]*w[i];dy[i]=dy[i-1]*w[i-2]*y[i];}}NTT(){setwy(level);}voidfft4(vector<mint>&a,intk){if((int)a.size()<=1)return;if(k==1){minta1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;return;}if(k&1){intv=1<<(k-1);for(intj=0;j<v;++j){mintajv=a[j+v];a[j+v]=a[j]-ajv;a[j]+=ajv;}}intu=1<<(2+(k&1));intv=1<<(k-2-(k&1));mintone=mint(1);mintimag=dw[1];while(v){// jh = 0{intj0=0;intj1=v;intj2=j1+v;intj3=j2+v;for(;j0<v;++j0,++j1,++j2,++j3){mintt0=a[j0],t1=a[j1],t2=a[j2],t3=a[j3];mintt0p2=t0+t2,t1p3=t1+t3;mintt0m2=t0-t2,t1m3=(t1-t3)*imag;a[j0]=t0p2+t1p3,a[j1]=t0p2-t1p3;a[j2]=t0m2+t1m3,a[j3]=t0m2-t1m3;}}// jh >= 1mintww=one,xx=one*dw[2],wx=one;for(intjh=4;jh<u;){ww=xx*xx,wx=ww*xx;intj0=jh*v;intje=j0+v;intj2=je+v;for(;j0<je;++j0,++j2){mintt0=a[j0],t1=a[j0+v]*xx,t2=a[j2]*ww,t3=a[j2+v]*wx;mintt0p2=t0+t2,t1p3=t1+t3;mintt0m2=t0-t2,t1m3=(t1-t3)*imag;a[j0]=t0p2+t1p3,a[j0+v]=t0p2-t1p3;a[j2]=t0m2+t1m3,a[j2+v]=t0m2-t1m3;}xx*=dw[__builtin_ctzll((jh+=4))];}u<<=2;v>>=2;}}voidifft4(vector<mint>&a,intk){if((int)a.size()<=1)return;if(k==1){minta1=a[1];a[1]=a[0]-a[1];a[0]=a[0]+a1;return;}intu=1<<(k-2);intv=1;mintone=mint(1);mintimag=dy[1];while(u){// jh = 0{intj0=0;intj1=v;intj2=v+v;intj3=j2+v;for(;j0<v;++j0,++j1,++j2,++j3){mintt0=a[j0],t1=a[j1],t2=a[j2],t3=a[j3];mintt0p1=t0+t1,t2p3=t2+t3;mintt0m1=t0-t1,t2m3=(t2-t3)*imag;a[j0]=t0p1+t2p3,a[j2]=t0p1-t2p3;a[j1]=t0m1+t2m3,a[j3]=t0m1-t2m3;}}// jh >= 1mintww=one,xx=one*dy[2],yy=one;u<<=2;for(intjh=4;jh<u;){ww=xx*xx,yy=xx*imag;intj0=jh*v;intje=j0+v;intj2=je+v;for(;j0<je;++j0,++j2){mintt0=a[j0],t1=a[j0+v],t2=a[j2],t3=a[j2+v];mintt0p1=t0+t1,t2p3=t2+t3;mintt0m1=(t0-t1)*xx,t2m3=(t2-t3)*yy;a[j0]=t0p1+t2p3,a[j2]=(t0p1-t2p3)*ww;a[j0+v]=t0m1+t2m3,a[j2+v]=(t0m1-t2m3)*ww;}xx*=dy[__builtin_ctzll(jh+=4)];}u>>=4;v<<=2;}if(k&1){u=1<<(k-1);for(intj=0;j<u;++j){mintajv=a[j]-a[j+u];a[j]+=a[j+u];a[j+u]=ajv;}}}voidntt(vector<mint>&a){if((int)a.size()<=1)return;fft4(a,__builtin_ctz(a.size()));}voidintt(vector<mint>&a){if((int)a.size()<=1)return;ifft4(a,__builtin_ctz(a.size()));mintiv=mint(a.size()).inverse();for(auto&x:a)x*=iv;}vector<mint>multiply(constvector<mint>&a,constvector<mint>&b){intl=a.size()+b.size()-1;if(min<int>(a.size(),b.size())<=40){vector<mint>s(l);for(inti=0;i<(int)a.size();++i)for(intj=0;j<(int)b.size();++j)s[i+j]+=a[i]*b[j];returns;}intk=2,M=4;while(M<l)M<<=1,++k;setwy(k);vector<mint>s(M);for(inti=0;i<(int)a.size();++i)s[i]=a[i];fft4(s,k);if(a.size()==b.size()&&a==b){for(inti=0;i<M;++i)s[i]*=s[i];}else{vector<mint>t(M);for(inti=0;i<(int)b.size();++i)t[i]=b[i];fft4(t,k);for(inti=0;i<M;++i)s[i]*=t[i];}ifft4(s,k);s.resize(l);mintinvm=mint(M).inverse();for(inti=0;i<l;++i)s[i]*=invm;returns;}voidntt_doubling(vector<mint>&a){intM=(int)a.size();autob=a;intt(b);mintr=1,zeta=mint(pr).pow((mint::get_mod()-1)/(M<<1));for(inti=0;i<M;i++)b[i]*=r,r*=zeta;ntt(b);copy(begin(b),end(b),back_inserter(a));}};#line 5 "ntt/arbitrary-ntt.hpp"
namespaceArbitraryNTT{usingi64=int64_t;usingu128=__uint128_t;constexprint32_tm0=167772161;constexprint32_tm1=469762049;constexprint32_tm2=754974721;usingmint0=LazyMontgomeryModInt<m0>;usingmint1=LazyMontgomeryModInt<m1>;usingmint2=LazyMontgomeryModInt<m2>;constexprintr01=mint1(m0).inverse().get();constexprintr02=mint2(m0).inverse().get();constexprintr12=mint2(m1).inverse().get();constexprintr02r12=i64(r02)*r12%m2;constexpri64w1=m0;constexpri64w2=i64(m0)*m1;template<typenameT,typenamesubmint>vector<submint>mul(constvector<T>&a,constvector<T>&b){staticNTT<submint>ntt;vector<submint>s(a.size()),t(b.size());for(inti=0;i<(int)a.size();++i)s[i]=i64(a[i]%submint::get_mod());for(inti=0;i<(int)b.size();++i)t[i]=i64(b[i]%submint::get_mod());returnntt.multiply(s,t);}template<typenameT>vector<int>multiply(constvector<T>&s,constvector<T>&t,intmod){autod0=mul<T,mint0>(s,t);autod1=mul<T,mint1>(s,t);autod2=mul<T,mint2>(s,t);intn=d0.size();vector<int>ret(n);constintW1=w1%mod;constintW2=w2%mod;for(inti=0;i<n;i++){intn1=d1[i].get(),n2=d2[i].get(),a=d0[i].get();intb=i64(n1+m1-a)*r01%m1;intc=(i64(n2+m2-a)*r02r12+i64(m2-b)*r12)%m2;ret[i]=(i64(a)+i64(b)*W1+i64(c)*W2)%mod;}returnret;}template<typenamemint>vector<mint>multiply(constvector<mint>&a,constvector<mint>&b){if(a.size()==0&&b.size()==0)return{};if(min<int>(a.size(),b.size())<128){vector<mint>ret(a.size()+b.size()-1);for(inti=0;i<(int)a.size();++i)for(intj=0;j<(int)b.size();++j)ret[i+j]+=a[i]*b[j];returnret;}vector<int>s(a.size()),t(b.size());for(inti=0;i<(int)a.size();++i)s[i]=a[i].get();for(inti=0;i<(int)b.size();++i)t[i]=b[i].get();vector<int>u=multiply<int>(s,t,mint::get_mod());vector<mint>ret(u.size());for(inti=0;i<(int)u.size();++i)ret[i]=mint(u[i]);returnret;}template<typenameT>vector<u128>multiply_u128(constvector<T>&s,constvector<T>&t){if(s.size()==0&&t.size()==0)return{};if(min<int>(s.size(),t.size())<128){vector<u128>ret(s.size()+t.size()-1);for(inti=0;i<(int)s.size();++i)for(intj=0;j<(int)t.size();++j)ret[i+j]+=i64(s[i])*t[j];returnret;}autod0=mul<T,mint0>(s,t);autod1=mul<T,mint1>(s,t);autod2=mul<T,mint2>(s,t);intn=d0.size();vector<u128>ret(n);for(inti=0;i<n;i++){i64n1=d1[i].get(),n2=d2[i].get();i64a=d0[i].get();i64b=(n1+m1-a)*r01%m1;i64c=((n2+m2-a)*r02r12+(m2-b)*r12)%m2;ret[i]=a+b*w1+u128(c)*w2;}returnret;}}// namespace ArbitraryNTT#line 14 "math/bigint.hpp"
namespaceMultiPrecisionIntegerImpl{structTENS{staticconstexprintoffset=30;constexprTENS():_tend(){_tend[offset]=1;for(inti=1;i<=offset;i++){_tend[offset+i]=_tend[offset+i-1]*10.0;_tend[offset-i]=1.0/_tend[offset+i];}}longdoubleten_ld(intn)const{assert(-offset<=nandn<=offset);return_tend[n+offset];}private:longdouble_tend[offset*2+1];};}// namespace MultiPrecisionIntegerImpl// 0 は neg=false, dat={} として扱うstructMultiPrecisionInteger{usingM=MultiPrecisionInteger;inlineconstexprstaticMultiPrecisionIntegerImpl::TENStens={};staticconstexprintD=1000000000;staticconstexprintlogD=9;boolneg;vector<int>dat;MultiPrecisionInteger():neg(false),dat(){}MultiPrecisionInteger(booln,constvector<int>&d):neg(n),dat(d){}template<typenameI,enable_if_t<internal::is_broadly_integral_v<I>>*=nullptr>MultiPrecisionInteger(Ix):neg(false){ifconstexpr(internal::is_broadly_signed_v<I>){if(x<0)neg=true,x=-x;}while(x)dat.push_back(x%D),x/=D;}MultiPrecisionInteger(conststring&S):neg(false){assert(!S.empty());if(S.size()==1u&&S[0]=='0')return;intl=0;if(S[0]=='-')++l,neg=true;for(intie=S.size();l<ie;ie-=logD){intis=max(l,ie-logD);longlongx=0;for(inti=is;i<ie;i++)x=x*10+S[i]-'0';dat.push_back(x);}while(!dat.empty()anddat.back()==0)dat.pop_back();}friendMoperator+(constM&lhs,constM&rhs){if(lhs.neg==rhs.neg)return{lhs.neg,_add(lhs.dat,rhs.dat)};if(_leq(lhs.dat,rhs.dat)){// |l| <= |r|autoc=_sub(rhs.dat,lhs.dat);booln=_is_zero(c)?false:rhs.neg;return{n,c};}autoc=_sub(lhs.dat,rhs.dat);booln=_is_zero(c)?false:lhs.neg;return{n,c};}friendMoperator-(constM&lhs,constM&rhs){returnlhs+(-rhs);}friendMoperator*(constM&lhs,constM&rhs){autoc=_mul(lhs.dat,rhs.dat);booln=_is_zero(c)?false:(lhs.neg^rhs.neg);return{n,c};}friendpair<M,M>divmod(constM&lhs,constM&rhs){autodm=_divmod_newton(lhs.dat,rhs.dat);booldn=_is_zero(dm.first)?false:lhs.neg!=rhs.neg;boolmn=_is_zero(dm.second)?false:lhs.neg;return{M{dn,dm.first},M{mn,dm.second}};}friendMoperator/(constM&lhs,constM&rhs){returndivmod(lhs,rhs).first;}friendMoperator%(constM&lhs,constM&rhs){returndivmod(lhs,rhs).second;}M&operator+=(constM&rhs){return(*this)=(*this)+rhs;}M&operator-=(constM&rhs){return(*this)=(*this)-rhs;}M&operator*=(constM&rhs){return(*this)=(*this)*rhs;}M&operator/=(constM&rhs){return(*this)=(*this)/rhs;}M&operator%=(constM&rhs){return(*this)=(*this)%rhs;}Moperator-()const{if(is_zero())return*this;return{!neg,dat};}Moperator+()const{return*this;}friendMabs(constM&m){return{false,m.dat};}boolis_zero()const{return_is_zero(dat);}friendbooloperator==(constM&lhs,constM&rhs){returnlhs.neg==rhs.neg&&lhs.dat==rhs.dat;}friendbooloperator!=(constM&lhs,constM&rhs){returnlhs.neg!=rhs.neg||lhs.dat!=rhs.dat;}friendbooloperator<(constM&lhs,constM&rhs){if(lhs==rhs)returnfalse;return_neq_lt(lhs,rhs);}friendbooloperator<=(constM&lhs,constM&rhs){if(lhs==rhs)returntrue;return_neq_lt(lhs,rhs);}friendbooloperator>(constM&lhs,constM&rhs){if(lhs==rhs)returnfalse;return_neq_lt(rhs,lhs);}friendbooloperator>=(constM&lhs,constM&rhs){if(lhs==rhs)returntrue;return_neq_lt(rhs,lhs);}// a * 10^b (1 <= |a| < 10) の形で渡す// 相対誤差:10^{-16} ~ 10^{-19} 程度 (処理系依存)pair<longdouble,int>dfp()const{if(is_zero())return{0,0};intl=max<int>(0,_size()-3);intb=logD*l;stringprefix{};for(inti=_size()-1;i>=l;i--){prefix+=_itos(dat[i],i!=_size()-1);}b+=prefix.size()-1;longdoublea=0;for(auto&c:prefix)a=a*10.0+(c-'0');a*=tens.ten_ld(-((int)prefix.size())+1);a=clamp<longdouble>(a,1.0,nextafterl(10.0,1.0));if(neg)a=-a;return{a,b};}stringto_string()const{if(is_zero())return"0";stringres;if(neg)res.push_back('-');for(inti=_size()-1;i>=0;i--){res+=_itos(dat[i],i!=_size()-1);}returnres;}longdoubleto_ld()const{auto[a,b]=dfp();if(-tens.offset<=bandb<=tens.offset){returna*tens.ten_ld(b);}returna*powl(10,b);}longlongto_ll()const{longlongres=_to_ll(dat);returnneg?-res:res;}__int128_tto_i128()const{__int128_tres=_to_i128(dat);returnneg?-res:res;}friendistream&operator>>(istream&is,M&m){strings;is>>s;m=M{s};returnis;}friendostream&operator<<(ostream&os,constM&m){returnos<<m.to_string();}// 内部の関数をテストstaticvoid_test_private_function(constM&,constM&);private:// sizeint_size()const{returndat.size();}// a == bstaticbool_eq(constvector<int>&a,constvector<int>&b){returna==b;}// a < bstaticbool_lt(constvector<int>&a,constvector<int>&b){if(a.size()!=b.size())returna.size()<b.size();for(inti=a.size()-1;i>=0;i--){if(a[i]!=b[i])returna[i]<b[i];}returnfalse;}// a <= bstaticbool_leq(constvector<int>&a,constvector<int>&b){return_eq(a,b)||_lt(a,b);}// a < b (s.t. a != b)staticbool_neq_lt(constM&lhs,constM&rhs){assert(lhs!=rhs);if(lhs.neg!=rhs.neg)returnlhs.neg;boolf=_lt(lhs.dat,rhs.dat);if(f)return!lhs.neg;returnlhs.neg;}// a == 0staticbool_is_zero(constvector<int>&a){returna.empty();}// a == 1staticbool_is_one(constvector<int>&a){return(int)a.size()==1&&a[0]==1;}// 末尾 0 を削除staticvoid_shrink(vector<int>&a){while(a.size()&&a.back()==0)a.pop_back();}// 末尾 0 を削除void_shrink(){while(_size()&&dat.back()==0)dat.pop_back();}// a + bstaticvector<int>_add(constvector<int>&a,constvector<int>&b){vector<int>c(max(a.size(),b.size())+1);for(inti=0;i<(int)a.size();i++)c[i]+=a[i];for(inti=0;i<(int)b.size();i++)c[i]+=b[i];for(inti=0;i<(int)c.size()-1;i++){if(c[i]>=D)c[i]-=D,c[i+1]++;}_shrink(c);returnc;}// a - bstaticvector<int>_sub(constvector<int>&a,constvector<int>&b){assert(_leq(b,a));vector<int>c{a};intborrow=0;for(inti=0;i<(int)a.size();i++){if(i<(int)b.size())borrow+=b[i];c[i]-=borrow;borrow=0;if(c[i]<0)c[i]+=D,borrow=1;}assert(borrow==0);_shrink(c);returnc;}// a * b (fft)staticvector<int>_mul_fft(constvector<int>&a,constvector<int>&b){if(a.empty()||b.empty())return{};autom=ArbitraryNTT::multiply_u128(a,b);vector<int>c;c.reserve(m.size()+3);__uint128_tx=0;for(inti=0;;i++){if(i>=(int)m.size()&&x==0)break;if(i<(int)m.size())x+=m[i];c.push_back(x%D);x/=D;}_shrink(c);returnc;}// a * b (naive)staticvector<int>_mul_naive(constvector<int>&a,constvector<int>&b){if(a.empty()||b.empty())return{};vector<longlong>prod(a.size()+b.size()-1+1);for(inti=0;i<(int)a.size();i++){for(intj=0;j<(int)b.size();j++){longlongp=1LL*a[i]*b[j];prod[i+j]+=p;if(prod[i+j]>=(4LL*D*D)){prod[i+j]-=4LL*D*D;prod[i+j+1]+=4LL*D;}}}vector<int>c(prod.size()+1);longlongx=0;inti=0;for(;i<(int)prod.size();i++)x+=prod[i],c[i]=x%D,x/=D;while(x)c[i]=x%D,x/=D,i++;_shrink(c);returnc;}// a * bstaticvector<int>_mul(constvector<int>&a,constvector<int>&b){if(_is_zero(a)||_is_zero(b))return{};if(_is_one(a))returnb;if(_is_one(b))returna;if(min<int>(a.size(),b.size())<=128){returna.size()<b.size()?_mul_naive(b,a):_mul_naive(a,b);}return_mul_fft(a,b);}// 0 <= A < 1e18, 1 <= B < 1e9staticpair<vector<int>,vector<int>>_divmod_li(constvector<int>&a,constvector<int>&b){assert(0<=(int)a.size()&&(int)a.size()<=2);assert((int)b.size()==1);longlongva=_to_ll(a);intvb=b[0];return{_integer_to_vec(va/vb),_integer_to_vec(va%vb)};}// 0 <= A < 1e18, 1 <= B < 1e18staticpair<vector<int>,vector<int>>_divmod_ll(constvector<int>&a,constvector<int>&b){assert(0<=(int)a.size()&&(int)a.size()<=2);assert(1<=(int)b.size()&&(int)b.size()<=2);longlongva=_to_ll(a),vb=_to_ll(b);return{_integer_to_vec(va/vb),_integer_to_vec(va%vb)};}// 1 <= B < 1e9staticpair<vector<int>,vector<int>>_divmod_1e9(constvector<int>&a,constvector<int>&b){assert((int)b.size()==1);if(b[0]==1)return{a,{}};if((int)a.size()<=2)return_divmod_li(a,b);vector<int>quo(a.size());longlongd=0;intb0=b[0];for(inti=a.size()-1;i>=0;i--){d=d*D+a[i];assert(d<1LL*D*b0);intq=d/b0,r=d%b0;quo[i]=q,d=r;}_shrink(quo);return{quo,d?vector<int>{int(d)}:vector<int>{}};}// 0 <= A, 1 <= Bstaticpair<vector<int>,vector<int>>_divmod_naive(constvector<int>&a,constvector<int>&b){if(_is_zero(b)){cerr<<"Divide by Zero Exception"<<endl;exit(1);}assert(1<=(int)b.size());if((int)b.size()==1)return_divmod_1e9(a,b);if(max<int>(a.size(),b.size())<=2)return_divmod_ll(a,b);if(_lt(a,b))return{{},a};// B >= 1e9, A >= Bintnorm=D/(b.back()+1);vector<int>x=_mul(a,{norm});vector<int>y=_mul(b,{norm});intyb=y.back();vector<int>quo(x.size()-y.size()+1);vector<int>rem(x.end()-y.size(),x.end());for(inti=quo.size()-1;i>=0;i--){if(rem.size()<y.size()){// do nothing}elseif(rem.size()==y.size()){if(_leq(y,rem)){quo[i]=1,rem=_sub(rem,y);}}else{assert(y.size()+1==rem.size());longlongrb=1LL*rem[rem.size()-1]*D+rem[rem.size()-2];intq=rb/yb;vector<int>yq=_mul(y,{q});// 真の商は q-2 以上 q+1 以下だが自信が無いので念のため while を回すwhile(_lt(rem,yq))q--,yq=_sub(yq,y);rem=_sub(rem,yq);while(_leq(y,rem))q++,rem=_sub(rem,y);quo[i]=q;}if(i)rem.insert(begin(rem),x[i-1]);}_shrink(quo),_shrink(rem);auto[q2,r2]=_divmod_1e9(rem,{norm});assert(_is_zero(r2));return{quo,q2};}// 0 <= A, 1 <= Bstaticpair<vector<int>,vector<int>>_divmod_dc(constvector<int>&a,constvector<int>&b);// 1 / a を 絶対誤差 B^{-deg} で求めるstaticvector<int>_calc_inv(constvector<int>&a,intdeg){assert(!a.empty()&&D/2<=a.back()anda.back()<D);intk=deg,c=a.size();while(k>64)k=(k+1)/2;vector<int>z(c+k+1);z.back()=1;z=_divmod_naive(z,a).first;while(k<deg){vector<int>s=_mul(z,z);s.insert(begin(s),0);intd=min(c,2*k+1);vector<int>t{end(a)-d,end(a)},u=_mul(s,t);u.erase(begin(u),begin(u)+d);vector<int>w(k+1),w2=_add(z,z);copy(begin(w2),end(w2),back_inserter(w));z=_sub(w,u);z.erase(begin(z));k*=2;}z.erase(begin(z),begin(z)+k-deg);returnz;}staticpair<vector<int>,vector<int>>_divmod_newton(constvector<int>&a,constvector<int>&b){if(_is_zero(b)){cerr<<"Divide by Zero Exception"<<endl;exit(1);}if((int)b.size()<=64)return_divmod_naive(a,b);if((int)a.size()-(int)b.size()<=64)return_divmod_naive(a,b);intnorm=D/(b.back()+1);vector<int>x=_mul(a,{norm});vector<int>y=_mul(b,{norm});ints=x.size(),t=y.size();intdeg=s-t+2;vector<int>z=_calc_inv(y,deg);vector<int>q=_mul(x,z);q.erase(begin(q),begin(q)+t+deg);vector<int>yq=_mul(y,{q});while(_lt(x,yq))q=_sub(q,{1}),yq=_sub(yq,y);vector<int>r=_sub(x,yq);while(_leq(y,r))q=_add(q,{1}),r=_sub(r,y);_shrink(q),_shrink(r);auto[q2,r2]=_divmod_1e9(r,{norm});assert(_is_zero(r2));return{q,q2};}// int -> string// 先頭かどうかに応じて zero padding するかを決めるstaticstring_itos(intx,boolzero_padding){assert(0<=x&&x<D);stringres;for(inti=0;i<logD;i++){res.push_back('0'+x%10),x/=10;}if(!zero_padding){while(res.size()&&res.back()=='0')res.pop_back();assert(!res.empty());}reverse(begin(res),end(res));returnres;}// convert ll to vectemplate<typenameI,enable_if_t<internal::is_broadly_integral_v<I>>*=nullptr>staticvector<int>_integer_to_vec(Ix){ifconstexpr(internal::is_broadly_signed_v<I>){assert(x>=0);}vector<int>res;while(x)res.push_back(x%D),x/=D;returnres;}staticlonglong_to_ll(constvector<int>&a){longlongres=0;for(inti=(int)a.size()-1;i>=0;i--)res=res*D+a[i];returnres;}static__int128_t_to_i128(constvector<int>&a){__int128_tres=0;for(inti=(int)a.size()-1;i>=0;i--)res=res*D+a[i];returnres;}staticvoid_dump(constvector<int>&a,strings=""){if(!s.empty())cerr<<s<<" : ";cerr<<"{ ";for(inti=0;i<(int)a.size();i++)cerr<<a[i]<<", ";cerr<<"}"<<endl;}};usingbigint=MultiPrecisionInteger;/**
* @brief 多倍長整数
*/#line 5 "verify/verify-aoj-ntl/aoj-ntl-2-f.test.cpp"
//intmain(){biginta,b;cin>>a>>b;cout<<a*b<<endl;}