#include <iostream>
#include <cmath>

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