function Main(input) {
    // inputにはすべての入力の文字列が与えられるので必要に応じて input.split("\n") などで分割する。
    var data = input.split('\n').slice(0,-1);
    data = data[0].split(' ');
    let a = data[0];
    let n = data[1];
    let sum = 1;
    let M = 1000000000;
    sum = a ** n;
    console.log(M);
    console.log(sum%M);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));