#include <iostream>
#include <cmath>

int main(){
    unsigned short a;
    unsigned long long n;
    std::cin >> a >> n;
    unsigned int r = 10000000;
    std::cout << r << std::endl << (unsigned long long)(std::pow(a, n)) % r << std::endl;
    return 0;
}