class="markdown_views prism-dracula">
#include
using namespace std;
#define N 1010
#define LL long long
#define fu(a,b,c) for(int a=b;a<=c;++a)
#define fd(a,b,c) for(int a=b;a>=c;--a)
const int Base=10000;
struct Big{
int len,w,t[N];
Big(){len=w=1;memset(t,0,sizeof(t));}
}ans;
Big change(int a){
Big c;c.len=0;
if(a<0)c.w=-1;
a=abs(a);
while(a)c.t[++c.len]=a%Base,a/=Base;
return c;
}
void print(Big c){
if(c.w==-1)printf("-");
printf("%d",c.t[c.len]);
fd(i,c.len-1,1)printf("%04d",c.t[i]);
printf("
");
}
bool unsigned_cmp(Big a,Big b){
if(a.len>b.len)return 1;
if(a.len<b.len)return 0;
fd(i,a.len,1){
if(a.t[i]>b.t[i])return 1;
if(a.t[i]<b.t[i])return 0;
}
return 1;
}
Big unsigned_add(Big a,Big b){
Big c;c.len=max(a.len,b.len);
fu(i,1,c.len)c.t[i]=a.t[i]+b.t[i];
fu(i,1,c.len){
if(c.t[i]>Base){
c.t[i]-=Base;
c.t[i+1]++;
if(i==c.len)c.len++;
}
}
return c;
}
Big unsigned_sub(Big a,Big b){
Big c;c.len=max(a.len,b.len);
fu(i,1,c.len)c.t[i]=a.t[i]-b.t[i];
fu(i,1,c.len){
if(c.t[i]<0){
c.t[i]+=Base;
c.t[i+1]--;
}
}
fd(i,c.len,1){
if(!c.t[i])c.len--;
else break;
}
return c;
}
Big add(Big a,Big b){
Big c;
if(unsigned_cmp(b,a))swap(a,b);
if(a.w==1&&b.w==1)c=unsigned_add(a,b),c.w=1;
if(a.w==1&&b.w==-1)c=unsigned_sub(a,b),c.w=1;
if(a.w==-1&&b.w==1)c=unsigned_sub(a,b),c.w=-1;
if(a.w==-1&&b.w==-1)c=unsigned_add(a,b),c.w=-1;
return c;
}
Big sub(Big a,Big b){b.w=0-b.w;return add(a,b);}
Big mul(Big a,Big b){
Big c;c.w=a.w*b.w;
c.len=a.len+b.len-1;
fu(i,1,a.len)
fu(j,1,b.len)
c.t[i+j-1]+=a.t[i]*b.t[j];
fu(i,1,c.len){
if(c.t[i]>Base){
c.t[i+1]+=c.t[i]/Base;
c.t[i]%=Base;
if(i==c.len)c.len++;
}
}
return c;
}
Big fast_pow(Big a,int b){
Big ans;ans.t[1]=1;
if((b&1)&&a.w==-1)ans.w=-1;
while(b){
if(b&1)ans=mul(ans,a);
b>>=1;
a=mul(a,a);
}
return ans;
}
int main(){
return 0;
}