#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#pragma GCC target("avx2")
#pragma GCC target("fma")
#include<bits/stdc++.h>
#include<immintrin.h>
using ui=unsigned;
using ll=long long;
using ull=unsigned long long;
using m256d=__m256d;
const double pi=acos(-1);
const m256d neg_mask=(m256d)(__v4di){ll(1ull<<63),ll(1ull<<63),ll(1ull<<63),ll(1ull<<63)};
struct cp4{
m256d real,imag;
__attribute__((always_inline)) inline cp4 operator + (const cp4 &b) const{
return {_mm256_add_pd(real,b.real),_mm256_add_pd(imag,b.imag)};
}
__attribute__((always_inline)) inline cp4 operator - (const cp4 &b) const{
return {_mm256_sub_pd(real,b.real),_mm256_sub_pd(imag,b.imag)};
}
__attribute__((always_inline)) inline cp4 operator * (const double x) const{
return {real*x,imag*x};
}
__attribute__((always_inline)) inline cp4 operator * (const cp4 &b) const{
return {_mm256_fmsub_pd(real,b.real,_mm256_mul_pd(imag,b.imag)),_mm256_fmadd_pd(real,b.imag,_mm256_mul_pd(imag,b.real))};
}
__attribute__((always_inline)) inline cp4 conj_rev() const{
return {_mm256_permute4x64_pd(real,27),_mm256_permute4x64_pd(_mm256_xor_pd(imag,neg_mask),27)};
}
__attribute__((always_inline)) inline void operator *= (const cp4 &b){
m256d t=_mm256_fmsub_pd(real,b.real,_mm256_mul_pd(imag,b.imag));
imag=_mm256_fmadd_pd(real,b.imag,_mm256_mul_pd(imag,b.real));
real=t;
}
void print(const char *sep=" ",const char *end="\n") const{
for (int i=0;i<4;i++) std::cout<<"("<<real[i]<<","<<imag[i]<<")"<<sep;
std::cout<<end;
}
};
namespace FFT_avx{
__attribute__((always_inline)) inline void mulcp(double &r0,double &i0,double r1,double i1){
double t=r0;
r0=r0*r1-i0*i1;
i0=t*i1+r1*i0;
}
template<class T>
__attribute__((always_inline)) inline void dif2(T &a,T &b){
T t0=a,t1=b;
a=t0+t1,b=t0-t1;
}
template<class T>
__attribute__((always_inline)) inline void dif_btf4(T &r0,T &i0,T &r1,T &i1,T &r2,T &i2,T &r3,T &i3){
dif2(r0,r2),dif2(i0,i2),dif2(r1,r3),dif2(i1,i3);
dif2(r2,i3),dif2(i2,r3);
std::swap(r2,i3),std::swap(i3,r3);
}
template<class T>
__attribute__((always_inline)) inline void dit_btf4(T &r0,T &i0,T &r1,T &i1,T &r2,T &i2,T &r3,T &i3){
dif2(r2,r3),dif2(i2,i3);
dif2(r0,r2),dif2(i0,i2),dif2(r1,i3),dif2(i1,r3);
std::swap(r1,i3),std::swap(i3,r3);
}
__attribute__((always_inline)) inline void dif4(cp4 &a){
dif_btf4(a.real[0],a.imag[0],a.real[1],a.imag[1],a.real[2],a.imag[2],a.real[3],a.imag[3]);
dif2(a.real[0],a.real[1]),dif2(a.imag[0],a.imag[1]);
}
__attribute__((always_inline)) inline void dit4(cp4 &a){
dif2(a.real[0],a.real[1]),dif2(a.imag[0],a.imag[1]);
dit_btf4(a.real[0],a.imag[0],a.real[1],a.imag[1],a.real[2],a.imag[2],a.real[3],a.imag[3]);
}
constexpr double w8_1_x=0.7071067811865476;
__attribute__((always_inline)) inline void dif8(cp4& a,cp4 &b){
dif_btf4(a.real[0],a.imag[0],a.real[2],a.imag[2],b.real[0],b.imag[0],b.real[2],b.imag[2]);
dif_btf4(a.real[1],a.imag[1],a.real[3],a.imag[3],b.real[1],b.imag[1],b.real[3],b.imag[3]);
mulcp(b.real[1],b.imag[1],w8_1_x,w8_1_x);
mulcp(b.real[3],b.imag[3],-w8_1_x,w8_1_x);
dif4(a);
dif2(b.real[0],b.real[1]),dif2(b.imag[0],b.imag[1]);
dif2(b.real[2],b.real[3]),dif2(b.imag[2],b.imag[3]);
}
__attribute__((always_inline)) inline void dit8(cp4& a,cp4 &b){
dit4(a);
dif2(b.real[0],b.real[1]),dif2(b.imag[0],b.imag[1]);
dif2(b.real[2],b.real[3]),dif2(b.imag[2],b.imag[3]);
mulcp(b.real[1],b.imag[1],w8_1_x,w8_1_x);
mulcp(b.real[3],b.imag[3],-w8_1_x,w8_1_x);
dit_btf4(a.real[0],a.imag[0],a.real[2],a.imag[2],b.real[0],b.imag[0],b.real[2],b.imag[2]);
dit_btf4(a.real[1],a.imag[1],a.real[3],a.imag[3],b.real[1],b.imag[1],b.real[3],b.imag[3]);
}
constexpr double w16_1_x=0.9238795325112867,w16_1_y=0.3826834323650898;
std::vector<std::vector<cp4>> rt,rt3;
std::vector<cp4> rtrev={(cp4){{-1,1,0,0},{0,0,-1,1}}};
__attribute__((always_inline)) inline void permute_rt(m256d &a,m256d &b){
m256d t0=_mm256_permute4x64_pd(a,216),t1=_mm256_permute4x64_pd(b,216);
a=_mm256_unpacklo_pd(t0,t1),b=_mm256_unpackhi_pd(t0,t1);
}
void init(int n){
if (n<8) n=8;
int nrt=rtrev.size();
if (nrt>=n) return;
rtrev.resize(n);
for (;nrt<n;nrt<<=1){
const std::complex<double> w=std::polar(1.,pi/(nrt<<2));
const cp4 w_4={_mm256_set1_pd(w.real()),_mm256_set1_pd(w.imag())};
for (int i=0;i<nrt;i++) rtrev[i+nrt]=rtrev[i]*w_4;
}
n=std::__lg(n);
if (rt.size()<3){
rt.resize(3),rt3.resize(3);
rt[2].resize(1),rt3[2].resize(1);
rt[2][0]=(cp4){{1,w16_1_x,w8_1_x,w16_1_y},{0,w16_1_y,w8_1_x,w16_1_x}};
rt3[2][0]=(cp4){{1,w16_1_y,-w8_1_x,-w16_1_x},{0,w16_1_x,w8_1_x,-w16_1_y}};
}
nrt=rt.size();
if (nrt>=n+1) return;
rt.resize(n+1),rt3.resize(n+1);
for (;nrt<=n;nrt++){
rt[nrt].resize(1<<(nrt-2));
const std::complex<double> w=std::polar(1.,pi/(1<<(nrt+1)));
const cp4 w_4={_mm256_set1_pd(w.real()),_mm256_set1_pd(w.imag())};
for (int j=0;j<(1<<(nrt-2));j+=2){
rt[nrt][j]=rt[nrt-1][j>>1];
rt[nrt][j+1]=rt[nrt-1][j>>1]*w_4;
permute_rt(rt[nrt][j].real,rt[nrt][j+1].real);
permute_rt(rt[nrt][j].imag,rt[nrt][j+1].imag);
}
rt3[nrt].resize(1<<(nrt-2));
const std::complex<double> w3=std::polar(1.,3*pi/(1<<(nrt+1)));
const cp4 w3_4={_mm256_set1_pd(w3.real()),_mm256_set1_pd(w3.imag())};
for (int j=0;j<(1<<(nrt-2));j+=2){
rt3[nrt][j]=rt3[nrt-1][j>>1];
rt3[nrt][j+1]=rt3[nrt-1][j>>1]*w3_4;
permute_rt(rt3[nrt][j].real,rt3[nrt][j+1].real);
permute_rt(rt3[nrt][j].imag,rt3[nrt][j+1].imag);
}
}
}
__attribute__((always_inline)) inline void dif16(cp4& a,cp4& b,cp4 &c,cp4 &d){
dif_btf4(a.real,a.imag,b.real,b.imag,c.real,c.imag,d.real,d.imag);
c*=FFT_avx::rt[2][0],d*=FFT_avx::rt3[2][0];
dif8(a,b),dif4(c),dif4(d);
}
__attribute__((always_inline)) inline void dit16(cp4& a,cp4& b,cp4 &c,cp4 &d){
dit8(a,b),dit4(c),dit4(d);
c*=FFT_avx::rt[2][0],d*=FFT_avx::rt3[2][0];
dit_btf4(a.real,a.imag,b.real,b.imag,c.real,c.imag,d.real,d.imag);
}
__attribute__((always_inline)) inline void dif32(cp4& a,cp4& b,cp4 &c,cp4 &d,cp4 &e,cp4 &f,cp4 &g,cp4 &h){
dif_btf4(a.real,a.imag,c.real,c.imag,e.real,e.imag,g.real,g.imag);
dif_btf4(b.real,b.imag,d.real,d.imag,f.real,f.imag,h.real,h.imag);
e*=FFT_avx::rt[3][0],f*=FFT_avx::rt[3][1];
g*=FFT_avx::rt3[3][0],h*=FFT_avx::rt3[3][1];
dif16(a,b,c,d),dif8(e,f),dif8(g,h);
}
__attribute__((always_inline)) inline void dit32(cp4& a,cp4& b,cp4 &c,cp4 &d,cp4 &e,cp4 &f,cp4 &g,cp4 &h){
dit16(a,b,c,d),dit8(e,f),dit8(g,h);
e*=FFT_avx::rt[3][0],f*=FFT_avx::rt[3][1];
g*=FFT_avx::rt3[3][0],h*=FFT_avx::rt3[3][1];
dit_btf4(a.real,a.imag,c.real,c.imag,e.real,e.imag,g.real,g.imag);
dit_btf4(b.real,b.imag,d.real,d.imag,f.real,f.imag,h.real,h.imag);
}
template<int n>
inline void dif_t(cp4 *a){
constexpr int h=n>>1,q=h>>1;
for (int i=0;i<q;i++) dif_btf4(a[i].real,a[i].imag,a[i+q].real,a[i+q].imag,a[i+q*2].real,a[i+q*2].imag,a[i+q*3].real,a[i+q*3].imag);
const auto &p=rt[std::__lg(n)],&p3=rt3[std::__lg(n)];
for (int i=0;i<q;i+=4){
a[q*2+i]*=p[i];
a[q*2+i+1]*=p[i+1];
a[q*2+i+2]*=p[i+2];
a[q*2+i+3]*=p[i+3];
}
for (int i=0;i<q;i+=4){
a[q*3+i]*=p3[i];
a[q*3+i+1]*=p3[i+1];
a[q*3+i+2]*=p3[i+2];
a[q*3+i+3]*=p3[i+3];
}
dif_t<h>(a),dif_t<q>(a+h),dif_t<q>(a+h+q);
}
template<>
__attribute__((always_inline)) inline void dif_t<1>(cp4 *a){dif4(*a);}
template<>
__attribute__((always_inline)) inline void dif_t<2>(cp4 *a){dif8(*a,a[1]);}
template<>
__attribute__((always_inline)) inline void dif_t<4>(cp4 *a){dif16(*a,a[1],a[2],a[3]);}
template<>
__attribute__((always_inline)) inline void dif_t<8>(cp4 *a){dif32(*a,a[1],a[2],a[3],a[4],a[5],a[6],a[7]);}
inline void dif(cp4 *a,int n){
switch(n){case 1:{dif_t<1>(a);break;}case 2:{dif_t<2>(a);break;}case 4:{dif_t<4>(a);break;}case 8:{dif_t<8>(a);break;}case 16:{dif_t<16>(a);break;}case 32:{dif_t<32>(a);break;}case 64:{dif_t<64>(a);break;}case 128:{dif_t<128>(a);break;}case 256:{dif_t<256>(a);break;}case 512:{dif_t<512>(a);break;}case 1024:{dif_t<1024>(a);break;}case 2048:{dif_t<2048>(a);break;}case 4096:{dif_t<4096>(a);break;}case 8192:{dif_t<8192>(a);break;}case 16384:{dif_t<16384>(a);break;}case 32768:{dif_t<32768>(a);break;}case 65536:{dif_t<65536>(a);break;}case 131072:{dif_t<131072>(a);break;}case 262144:{dif_t<262144>(a);break;}case 524288:{dif_t<524288>(a);break;}case 1048576:{dif_t<1048576>(a);break;}case 2097152:{dif_t<2097152>(a);break;}case 4194304:{dif_t<4194304>(a);break;}case 8388608:{dif_t<8388608>(a);break;}case 16777216:{dif_t<16777216>(a);break;}}
}
template<int n>
void dit_t(cp4 *a){
constexpr int h=n>>1,q=h>>1;
dit_t<h>(a),dit_t<q>(a+h),dit_t<q>(a+h+q);
const auto &p=rt[std::__lg(n)],&p3=rt3[std::__lg(n)];
for (int i=0;i<q;i+=4){
a[q*2+i]*=p[i];
a[q*2+i+1]*=p[i+1];
a[q*2+i+2]*=p[i+2];
a[q*2+i+3]*=p[i+3];
}
for (int i=0;i<q;i+=4){
a[q*3+i]*=p3[i];
a[q*3+i+1]*=p3[i+1];
a[q*3+i+2]*=p3[i+2];
a[q*3+i+3]*=p3[i+3];
}
for (int i=0;i<q;i++) dit_btf4(a[i].real,a[i].imag,a[i+q].real,a[i+q].imag,a[i+q*2].real,a[i+q*2].imag,a[i+q*3].real,a[i+q*3].imag);
}
template<>
__attribute__((always_inline)) inline void dit_t<1>(cp4 *a){dit4(*a);}
template<>
__attribute__((always_inline)) inline void dit_t<2>(cp4 *a){dit8(*a,a[1]);}
template<>
__attribute__((always_inline)) inline void dit_t<4>(cp4 *a){dit16(*a,a[1],a[2],a[3]);}
template<>
__attribute__((always_inline)) inline void dit_t<8>(cp4 *a){dit32(*a,a[1],a[2],a[3],a[4],a[5],a[6],a[7]);}
inline void dit(cp4 *a,int n){
switch (n){case 1:{dit_t<1>(a);break;}case 2:{dit_t<2>(a);break;}case 4:{dit_t<4>(a);break;}case 8:{dit_t<8>(a);break;}case 16:{dit_t<16>(a);break;}case 32:{dit_t<32>(a);break;}case 64:{dit_t<64>(a);break;}case 128:{dit_t<128>(a);break;}case 256:{dit_t<256>(a);break;}case 512:{dit_t<512>(a);break;}case 1024:{dit_t<1024>(a);break;}case 2048:{dit_t<2048>(a);break;}case 4096:{dit_t<4096>(a);break;}case 8192:{dit_t<8192>(a);break;}case 16384:{dit_t<16384>(a);break;}case 32768:{dit_t<32768>(a);break;}case 65536:{dit_t<65536>(a);break;}case 131072:{dit_t<131072>(a);break;}case 262144:{dit_t<262144>(a);break;}case 524288:{dit_t<524288>(a);break;}case 1048576:{dit_t<1048576>(a);break;}case 2097152:{dit_t<2097152>(a);break;}case 4194304:{dit_t<4194304>(a);break;}case 8388608:{dit_t<8388608>(a);break;}case 16777216:{dit_t<16777216>(a);break;}}
}
__attribute__((always_inline)) inline void conv_k2(std::complex<double> &a_2,std::complex<double> &a_3,const std::complex<double> &b_2,const std::complex<double> &b_3){
std::complex<double> a1=a_2+std::conj(a_3),a2=a_2-std::conj(a_3);
std::complex<double> b1=b_2+std::conj(b_3),b2=b_2-std::conj(b_3);
std::complex<double> u=a1*b1+a2*b2*std::complex<double>(0,-1),v=a1*b2+a2*b1;
a_2=u+v,a_3=std::conj(u-v);
}
__attribute__((always_inline)) inline void conv_k4_47(std::complex<double> &a_4,std::complex<double> &a_7,const std::complex<double> &b_4,const std::complex<double> &b_7){
std::complex<double> a1=a_4+std::conj(a_7),a2=a_4-std::conj(a_7);
std::complex<double> b1=b_4+std::conj(b_7),b2=b_4-std::conj(b_7);
std::complex<double> u=a1*b1+a2*b2*std::complex<double>(-w8_1_x,-w8_1_x),v=a1*b2+a2*b1;
a_4=u+v,a_7=std::conj(u-v);
}
__attribute__((always_inline)) inline void conv_k4_56(std::complex<double> &a_5,std::complex<double> &a_6,const std::complex<double> &b_5,const std::complex<double> &b_6){
std::complex<double> a1=a_5+std::conj(a_6),a2=a_5-std::conj(a_6);
std::complex<double> b1=b_5+std::conj(b_6),b2=b_5-std::conj(b_6);
std::complex<double> u=a1*b1+a2*b2*std::complex<double>(w8_1_x,w8_1_x),v=a1*b2+a2*b1;
a_5=u+v,a_6=std::conj(u-v);
}
inline void conv(cp4 *a,cp4 *b,int n){
init(n);
dif(a,n),dif(b,n);
const double r=0.25/n,qr=0.25*r;
std::complex<double> t={a->real[0]*b->real[0]+a->imag[0]*b->imag[0],a->real[0]*b->imag[0]+a->imag[0]*b->real[0]};
t*=r;
a->real[0]=t.real(),a->imag[0]=t.imag();
mulcp(a->real[1],a->imag[1],b->real[1]*r,b->imag[1]*r);
std::complex<double> a_2(a->real[2],a->imag[2]),a_3(a->real[3],a->imag[3]);
conv_k2(a_2,a_3,{b->real[2],b->imag[2]},{b->real[3],b->imag[3]});
a_2*=qr,a_3*=qr;
a->real[2]=a_2.real(),a->imag[2]=a_2.imag();
a->real[3]=a_3.real(),a->imag[3]=a_3.imag();
std::complex<double> a_4(a[1].real[0],a[1].imag[0]),a_7(a[1].real[3],a[1].imag[3]);
conv_k4_47(a_4,a_7,{b[1].real[0],b[1].imag[0]},{b[1].real[3],b[1].imag[3]});
a_4*=qr,a_7*=qr;
a[1].real[0]=a_4.real(),a[1].imag[0]=a_4.imag();
a[1].real[3]=a_7.real(),a[1].imag[3]=a_7.imag();
std::complex<double> a_5(a[1].real[1],a[1].imag[1]),a_6(a[1].real[2],a[1].imag[2]);
conv_k4_56(a_5,a_6,{b[1].real[1],b[1].imag[1]},{b[1].real[2],b[1].imag[2]});
a_5*=qr,a_6*=qr;
a[1].real[1]=a_5.real(),a[1].imag[1]=a_5.imag();
a[1].real[2]=a_6.real(),a[1].imag[2]=a_6.imag();
for (int k=2,m=3;k<n;k+=k,m+=m){
for (int i=k,j=k+k-1;i<m;i++,j--){
cp4 a1=a[i]+a[j].conj_rev(),a2=a[i]-a[j].conj_rev();
cp4 b1=b[i]+b[j].conj_rev(),b2=b[i]-b[j].conj_rev();
cp4 u=a1*b1+a2*b2*rtrev[i],v=a1*b2+a2*b1;
a[i]=(u+v)*qr,a[j]=((u-v).conj_rev())*qr;
}
}
dit(a,n);
}
}
constexpr int base=100000000,digit=8;
constexpr int FFTbase=10000;
using namespace std;
struct BigInt{
bool sign;
vector<int> a;
BigInt(){sign=false,a.resize(1);}
BigInt(ll x){
a.clear();
if(x<0) sign=true,x=-x;
else sign=false;
do{
a.push_back(x%base);
x/=base;
}while(x);
}
inline void fix(){
while (not a.empty() and a.back()==0) a.pop_back();
if (a.empty()) a.push_back(0),sign=false;
// assert(find_if(a.begin(),a.end(),[](int x){return x>=base or x<0;})==a.end());
}
BigInt(const string &buf){
assert(count(buf.begin(),buf.end(),'-')<=1);
sign=false;
a.clear();
for (int i=buf.length()-1,j=base;i>=0;i--){
if (buf[i]=='-') sign=true;
else if (isdigit(buf[i])){
if (j==base) a.push_back(0),j=1;
a.back()+=j*(buf[i]^48);
j*=10;
}
}
fix();
}
operator string() const{
stringstream buf;
if (sign) buf<<"-";
buf<<a.back();
for (int i=a.size()-2;i>=0;i--) buf<<setw(digit)<<setfill('0')<<a[i];
return buf.str();
}
ull to_int() const{
ull ans=0;
for (int i=a.size()-1;i>=0;i--) ans*=base,ans+=a[i];
return ans;
}
friend istream& operator >> (istream &in,BigInt &a){
string buf;
in>>buf;
a=BigInt(buf);
return in;
}
friend ostream& operator << (ostream &out,const BigInt &a){
if (a.sign) out<<"-";
out<<a.a.back();
for (int i=a.a.size()-2;i>=0;i--) out<<setw(digit)<<setfill('0')<<a.a[i];
return out;
}
BigInt& operator *= (const BigInt &b){
if (a.size()<=16 or b.a.size()<=16){
vector<int> tmp(a.size()+b.a.size());
for (ui i=0;i<a.size();i++){
for (ui j=0;j<b.a.size();j++){
ll u=ll(a[i])*b.a[j]+tmp[i+j];
tmp[i+j]=u%base;
tmp[i+j+1]+=u/base;
}
}
a=tmp;
sign^=b.sign;
fix();
return *this;
}else{
int len=1<<(__lg(a.size()+b.a.size()-1)+1);
cp4 *f=(cp4*)_mm_malloc(sizeof(cp4)*(len>>2),256),*g=(cp4*)_mm_malloc(sizeof(cp4)*(len>>2),256);
memset(f,0,sizeof(cp4)*(len>>2)),memset(g,0,sizeof(cp4)*(len>>2));
for (ui i=0;i<a.size()-3;i+=4) f[i>>2]=(cp4){{double(a[i]%FFTbase),double(a[i+1]%FFTbase),double(a[i+2]%FFTbase),double(a[i+3]%FFTbase)},{double(a[i]/FFTbase),double(a[i+1]/FFTbase),double(a[i+2]/FFTbase),double(a[i+3]/FFTbase)}};
if ((a.size()&3)==3) f[a.size()>>2]=(cp4){{double(a[a.size()-3]%FFTbase),double(a[a.size()-2]%FFTbase),double(a[a.size()-1]%FFTbase),0},{double(a[a.size()-3]/FFTbase),double(a[a.size()-2]/FFTbase),double(a[a.size()-1]/FFTbase),0}};
else if ((a.size()&3)==2) f[a.size()>>2]=(cp4){{double(a[a.size()-2]%FFTbase),double(a[a.size()-1]%FFTbase),0,0},{double(a[a.size()-2]/FFTbase),double(a[a.size()-1]/FFTbase),0,0}};
else if ((a.size()&3)==1) f[a.size()>>2]=(cp4){{double(a[a.size()-1]%FFTbase),0,0,0},{double(a[a.size()-1]/FFTbase),0,0,0}};
for (ui i=0;i<b.a.size()-3;i+=4) g[i>>2]=(cp4){{double(b.a[i]%FFTbase),double(b.a[i+1]%FFTbase),double(b.a[i+2]%FFTbase),double(b.a[i+3]%FFTbase)},{double(b.a[i]/FFTbase),double(b.a[i+1]/FFTbase),double(b.a[i+2]/FFTbase),double(b.a[i+3]/FFTbase)}};
if ((b.a.size()&3)==3) g[b.a.size()>>2]=(cp4){{double(b.a[b.a.size()-3]%FFTbase),double(b.a[b.a.size()-2]%FFTbase),double(b.a[b.a.size()-1]%FFTbase),0},{double(b.a[b.a.size()-3]/FFTbase),double(b.a[b.a.size()-2]/FFTbase),double(b.a[b.a.size()-1]/FFTbase),0}};
else if ((b.a.size()&3)==2) g[b.a.size()>>2]=(cp4){{double(b.a[b.a.size()-2]%FFTbase),double(b.a[b.a.size()-1]%FFTbase),0,0},{double(b.a[b.a.size()-2]/FFTbase),double(b.a[b.a.size()-1]/FFTbase),0,0}};
else if ((b.a.size()&3)==1) g[b.a.size()>>2]=(cp4){{double(b.a[b.a.size()-1]%FFTbase),0,0,0},{double(b.a[b.a.size()-1]/FFTbase),0,0,0}};
FFT_avx::conv(f,g,len>>2);
ll tmp=0;
a.resize(a.size()+b.a.size());
vector<complex<double>> res;
res.reserve(len);
for (int i=0;i<(len>>2);i++){
for (int j=0;j<4;j++) res.push_back(complex<double>(f[i].real[j],f[i].imag[j]));
}
reverse(res.begin()+1,res.end());
for (int i=0;i<int(a.size());i++){
tmp+=(ll(res[i].real()+0.5)+ll(res[i].imag()+0.5)*FFTbase);
a[i]=tmp%base;
tmp/=base;
}
sign^=b.sign;
fix();
_mm_free(f),_mm_free(g);
return *this;
}
}
};
using namespace std;
static inline ull GetCycleCount(){
unsigned hi,lo;
__asm__ volatile("rdtsc":"=a"(lo),"=d"(hi));
return (ull(hi)<<32)|lo;
}
unsigned itc[10000];
inline void init_output_table(){
int cnt=0;
for (int i=0;i<10;i++){
for (int j=0;j<10;j++){
for (int k=0;k<10;k++){
for (int l=0;l<10;l++){
itc[cnt++]=(i|(j<<8)|(k<<16)|(l<<24))+808464432;
}
}
}
}
}
char buf[2000200];
int main(){
init_output_table();
BigInt a,b;
a.a.clear();
a.a.reserve(260000);
b.a.clear();
b.a.reserve(260000);
int n=fread(buf,1,2000100,stdin);
char *c=buf,*x=c;
c+=n;
while (not isdigit(*c)) c--;
for (int j=base;isdigit(*c);c--){
if (j==base) b.a.push_back(0),j=1;
b.a.back()+=j*(*c^48);
j*=10;
}
while (not isdigit(*c)) c--;
for (int j=base;c>=x;c--){
if (j==base) a.a.push_back(0),j=1;
a.a.back()+=j*(*c^48);
j*=10;
}
a*=b;
char *p=buf;
for (int i=a.a.size()-1;i>=0;i--,p+=8){
memcpy(p,&itc[a.a[i]/10000],sizeof(unsigned));
memcpy(p+4,&itc[a.a[i]%10000],sizeof(unsigned));
}
char *q=buf;
while (*q=='0') q++;
fwrite(q,1,p-q,stdout);
// BigInt a,b;
// cin>>a>>b;
// // BigInt a(string(1000000,'9')),b(string(1000000,'9'));
// cout<<(a*=b);
// for (int i=0;i<8;i++) a[i]=(cp4){{i*4+1.,i*4+2.,i*4+3.,i*4+4.},{i*4+33.,i*4+34.,i*4+35.,i*4+36.}};
// for (int i=0;i<8;i++) b[i]=(cp4){{i*4+33.,i*4+34.,i*4+35.,i*4+36.},{i*4+1.,i*4+2.,i*4+3.,i*4+4.}};
// FFT_avx::conv(a,b,8);
// for (int i=0;i<8;i++) a[i].print("\n","");
// cp4 a={{1,3,5,7},{2,4,6,8}};
// a.print();
// a=a.conj_rev();
// a.print();
// FFT_avx::init(131072);
// for (int i=0;i<131072;i++) a[i]=(cp4){{i*4e-6,(i+1)*4e-6,(i+3)*4e-6,(i+4)*4e-6},{0,0,0,0}};
// ull st=GetCycleCount();
// auto st_t=clock();
// FFT_avx::dif(a,131072);
// std::cout<<(GetCycleCount()-st)*1e-9<<"G cycles"<<"\n";
// cout<<clock()-st_t;
return 0;
}
| Compilation | N/A | N/A | Compile Error | Score: N/A | 显示更多 |