#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 LMULT3(short a[],short b[],short c[],int k,double d[],double e[],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[N],e[N],f[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(1){
		if(y&1)LMULT3(a,b,a,k,d,e,f,t);
		y>>=1;
		if(!y)break;
		LSQUARE(b,b,k,d,e,t);
		i*=2;
		k=(int)ceil(log2(ceil(2*i*r/4)));
	}
	if(!k)k++;
	SUBn(a,c,a,k);
	end=clock();
	printf("%.3fs\n",(double)(end-start)/CLOCKS_PER_SEC);
	for(i=4;i--;)printf("%04d",a[i]);
	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 INV2(double d[],short c[],int k,long long t[]){
	int i,k2=1<<k;
	for(i=(1<<k)/2;i--;)d[1+i*2]*=-1;
	for(i=0;i<k2;i++)t[i]=(long long)(d[i]/(k2/2)+0.5);
	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 MID3(double d[],double e[],double f[],int k){
	int i,j,k2;
	double s[4],t[2],u[2],r,pr;
	k2=1<<k;
	f[0+0*2]=d[0+0*2]*e[0+0*2]+d[1+0*2]*e[1+0*2];
	f[1+0*2]=d[0+0*2]*e[1+0*2]+d[1+0*2]*e[0+0*2];
	pr=-PI/(k2/4);
	for(i=1,j=k2/2-1;i<k2/4;i++,j--){
		r=i*pr;
		u[0]=cos(r)+1;
		u[1]=sin(r);
		s[0]=d[0+i*2]-d[0+j*2];
		s[1]=d[1+i*2]+d[1+j*2];
		s[2]=e[0+i*2]-e[0+j*2];
		s[3]=e[1+i*2]+e[1+j*2];
		t[0]=-s[0]*s[3]-s[1]*s[2];
		t[1]=+s[0]*s[2]-s[1]*s[3];
		f[0+i*2]=-0.25*(+t[0]*u[1]+t[1]*u[0])+d[0+i*2]*e[0+i*2]-d[1+i*2]*e[1+i*2];
		f[1+i*2]=+0.25*(-t[1]*u[1]+t[0]*u[0])+d[0+i*2]*e[1+i*2]+d[1+i*2]*e[0+i*2];
		f[0+j*2]=-0.25*(+t[0]*u[1]+t[1]*u[0])+d[0+j*2]*e[0+j*2]-d[1+j*2]*e[1+j*2];
		f[1+j*2]=-0.25*(-t[1]*u[1]+t[0]*u[0])+d[0+j*2]*e[1+j*2]+d[1+j*2]*e[0+j*2];
	}
	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]);
	for(i=0;i<k2/2;i++){
		j=tib(i,k-1);
		d[0+j*2]=f[0+i*2];
		d[1+j*2]=-f[1+i*2];
	}
	return;
}

void LMULT3(short a[],short b[],short c[],int k,double d[],double e[],double f[],long long t[]){
	if(k<3)k=3;
	PRE2(a,d,k-1);
	FFT(d,k-1);
	PRE2(b,e,k-1);
	FFT(e,k-1);
	MID3(d,e,f,k);
	FFT(d,k-1);
	INV2(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);
	MID3(d,d,f,k);
	FFT(d,k-1);
	INV2(d,c,k,t);
	return;
}