#include<stdio.h>

int main(void)
{
	long long int a,n,b=1;
	scanf("%lld %lld",&a,&n);
	for(int i=0;i<n;i++)
		b*=a;
	int M=10000000;
	printf("%d\n",M);
	printf("%lld\n",b%M);
	return 0;
}