#include <iostream>
#include <cmath>

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