use std::io::stdin;

fn main() {
    let m: u64 = 10_000_000;

    let mut line: String = String::new();
    stdin().read_line(&mut line).ok();

    let nlist: Vec<u64> = line.trim().split_whitespace().map(|e| e.parse().unwrap()).collect();
    let a: u64 = nlist[0];
    let n: u32 = nlist[1] as u32;

    println!("{}", m);
    println!("{}", a.pow(n)%m);
}