#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define PI 3.1415926535897932384626433832795
#define base 10000
#define K 23
#define N (1<<K)
void LMULT(short a[],short b[],short c[],int k,double d[],double f[],long long t[]);
void LSQUARE(short a[],short c[],int k,double d[],double f[],long long t[]);
void SUBn(short a[],short b[],short c[],int n);

int main(void){
    clock_t start,end;
	static short a[N],b[N],c[N];
	static long long t[N];
	static double d[2*N],e[2*N];
	int i,k,x,y;
	double r;
	printf("x^yの形で入力\n");
	scanf("%d^%d",&x,&y);
	start=clock();
	r=log10(x);
	k=(int)ceil(log2(ceil(2*r/4)));
	a[0]=1;
	b[0]=x%base;
	b[1]=x/base;
	c[0]=1;
	i=1;
	while(y){
		if(y&1)LMULT(a,b,a,k,d,e,t);
		y>>=1;
		if(!y)break;
		LSQUARE(b,b,k,d,e,t);
		i*=2;
		k=(int)ceil(log2(ceil(2*i*r/4)));
	}
	SUBn(a,c,a,k);
	end=clock();
	printf("%.3fs\n",(double)(end-start)/CLOCKS_PER_SEC);
	//for(i=N;i--;)printf("%04d")
	return 0;
}

void SUBn(short a[],short b[],short c[],int n){
	int i;
	int t=0;
	for(i=0;i<n;i++){
		t+=a[i]-b[i]+base;
		c[i]=t%base;
		t/=base;
		t--;
	}
	return;
}

int tib(int a,int k){
	int i=k,z=0;
	while(i--){
		z=(z<<1)+(a&1);
		a>>=1;
	}
	return z;
}

void PRE(short a[],short b[],double d[],int k){
	int i,j;
	for(i=0;i<(1<<k);i++){
		j=tib(i,k);
		d[0+i*2]=(double)a[j];
		d[1+i*2]=(double)b[j];
	}
	return;
}

void MID(double d[],double f[],int k){
	int i,j,k2;
	k2=1<<k;
	f[0+0*2]=d[0+0*2]*d[1+0*2];
	f[1+0*2]=0.0;
	for(i=1,j=k2-1;i<k2/2;i++,j--){
		f[0+i*2]=(d[0+i*2]*d[1+i*2]+d[0+j*2]*d[1+j*2])*0.5;
		f[1+i*2]=(-d[0+i*2]*d[0+i*2]+d[1+i*2]*d[1+i*2]+d[0+j*2]*d[0+j*2]-d[1+j*2]*d[1+j*2])*0.25;
	}
	f[0+k2]=d[0+k2]*d[1+k2];
	f[1+k2]=0.0;
	i=0;
	j=tib(i,k);
	d[0+j*2]=f[0+i*2];
	d[1+j*2]=-f[1+i*2];
	i=k2/2;
	j=tib(k2-i,k);
	d[0+j*2]=f[0+i*2];
	d[1+j*2]=-f[1+i*2];
	for(i=1;i<k2/2;){
		j=tib(i,k);
		d[0+j*2]=f[0+i*2];
		d[1+j*2]=-f[1+i*2];
		j=tib(k2-i,k);
		d[0+j*2]=f[0+i*2];
		d[1+j*2]=f[1+i*2];
		i++;
	}
	return;
}

void INV(double d[],short c[],int k,long long t[]){
	int i,k2=1<<k;
	for(i=0;i<k2;i++)t[i]=(long long)round(d[0+i*2]/k2);
	for(i=0;i<k2;i++){
		c[i]=t[i]%base;
		t[i+1]+=t[i]/base;
	}
	return;
}

void FFT(double d[],int k){
	int i,j,k5,k2=1<<k,cnt;
	double t[2],r,pr;
	for(i=0;i<k2*2;i+=4){
		t[0]=d[i+2];
		t[1]=d[i+3];
		d[i+2]=d[i+0]-t[0];
		d[i+3]=d[i+1]-t[1];
		d[i+0]+=t[0];
		d[i+1]+=t[1];
	}
	for(i=0;i<k2*2;i+=8){
		t[0]=d[i+4];
		t[1]=d[i+5];
		d[i+4]=d[i+0]-t[0];
		d[i+5]=d[i+1]-t[1];
		d[i+0]+=t[0];
		d[i+1]+=t[1];
		t[0]=       +d[i+7];
		t[1]=-d[i+6]       ;
		d[i+6]=d[i+2]-t[0];
		d[i+7]=d[i+3]-t[1];
		d[i+2]+=t[0];
		d[i+3]+=t[1];
	}
	for(j=2;j<k;j++){
		k5=1<<j;
		pr=PI/k5;
		for(i=0;i<k2;i+=k5){
			for(cnt=0;cnt<k5;cnt++){
				r=pr*cnt;
				t[0]= cos(r)*d[0+(i+k5)*2]+sin(r)*d[1+(i+k5)*2];
				t[1]=-sin(r)*d[0+(i+k5)*2]+cos(r)*d[1+(i+k5)*2];
				d[0+(i+k5)*2]=d[0+i*2]-t[0];
				d[1+(i+k5)*2]=d[1+i*2]-t[1];
				d[0+i*2]+=t[0];
				d[1+i*2]+=t[1];
				i++;
			}
		}
	}
	return;
}

void PRE2(short a[],double d[],int k){
	int i,j;
	for(i=0;i<(1<<k)*2;i++){
		j=tib(i,k);
		d[0+i*2]=(double)a[0+j*2];
		d[1+i*2]=(double)a[1+j*2];
	}
	return;
}


void MID2(double d[],double e[],double f[],int k){
	int i,j,k2;
	double s[2],t[2],u[2],v[2],w[2],x[2],y[2],r,pr;
	k2=1<<k;
	f[0+0*2]=(d[0+0*2]+d[1+0*2])*(e[0+0*2]+e[1+0*2]);
	f[1+0*2]=0.0;
	f[0+k2 ]=(d[0+0*2]-d[1+0*2])*(e[0+0*2]-e[1+0*2]);
	f[1+k2 ]=0.0;
	pr=PI/(k2/2);
	for(i=1,j=k2/2-1;i<k2/4;i++,j--){
		r=i*pr;
		u[0]=0.5*(1+sin(r));
		u[1]=0.5*cos(r);
		s[0]=d[0+i*2]-d[0+j*2];
		s[1]=d[1+i*2]+d[1+j*2];
		t[0]=e[0+i*2]-e[0+j*2];
		t[1]=e[1+i*2]+e[1+j*2];
		v[0]=u[0]*s[0]-u[1]*s[1];
		v[1]=u[0]*s[1]+u[1]*s[0];
		w[0]=u[0]*t[0]-u[1]*t[1];
		w[1]=u[0]*t[1]+u[1]*t[0];
		x[0]=d[0+i*2]-v[0];
		x[1]=d[1+i*2]-v[1];
		y[0]=e[0+i*2]-w[0];
		y[1]=e[1+i*2]-w[1];
		f[0+i*2]=x[0]*y[0]-x[1]*y[1];
		f[1+i*2]=x[0]*y[1]+x[1]*y[0];
		x[0]=d[0+j*2]+v[0];
		x[1]=-(-d[1+j*2]+v[1]);
		y[0]=e[0+j*2]+w[0];
		y[1]=-(-e[1+j*2]+w[1]);
		f[0+j*2]=x[0]*y[0]-x[1]*y[1];
		f[1+j*2]=x[0]*y[1]+x[1]*y[0];
	}
	f[0+k2/2]=d[0+k2/2]*e[0+k2/2]-d[1+k2/2]*e[1+k2/2];
	f[1+k2/2]=-(d[0+k2/2]*e[1+k2/2]+d[1+k2/2]*e[0+k2/2]);
	i=0;
	j=tib(i,k);
	d[0+j*2]=f[0+i*2];
	d[1+j*2]=-f[1+i*2];
	i=k2/2;
	j=tib(k2-i,k);
	d[0+j*2]=f[0+i*2];
	d[1+j*2]=-f[1+i*2];
	for(i=1;i<k2/2;){
		j=tib(i,k);
		d[0+j*2]=f[0+i*2];
		d[1+j*2]=-f[1+i*2];
		j=tib(k2-i,k);
		d[0+j*2]=f[0+i*2];
		d[1+j*2]=f[1+i*2];
		i++;
	}
	return;
}

void LMULT(short a[],short b[],short c[],int k,double d[],double f[],long long t[]){
	if(k<3)k=3;
	PRE(a,b,d,k);
	FFT(d,k);
	MID(d,f,k);
	FFT(d,k);
	INV(d,c,k,t);
	return;
}

void LSQUARE(short a[],short c[],int k,double d[],double f[],long long t[]){
	if(k<3)k=3;
	PRE2(a,d,k-1);
	FFT(d,k-1);
	MID2(d,d,f,k);
	FFT(d,k);
	INV(d,c,k,t);
	return;
}