For given integers m and n, compute mn (mod 1,000,000,007). Here, A (mod M) is the remainder when A is divided by M.

Constraints

* 1 ≤ m ≤ 100
* 1 ≤ n ≤ 109

Input


m n


Two integers m and n are given in a line.

Output

Print mn (mod 1,000,000,007) in a line.

Examples

Input

2 3


Output

8


Input

5 8


Output

390625
mod utils {
    use std::error::Error;
    use std::io::stdin;
    use std::str::FromStr;

    #[allow(dead_code)]
    pub fn read_line<T>() -> Result<Vec<T>, Box<Error>>
    where
        T: FromStr,
        T::Err: 'static + Error,
    {
        let mut line = String::new();
        let _ = stdin().read_line(&mut line)?;
        let parsed_line = line.split_whitespace()
            .map(|x| x.parse::<T>())
            .collect::<Result<Vec<T>, T::Err>>()?;

        Ok(parsed_line)
    }

    #[allow(dead_code)]
    pub fn read_lines<T>(n: usize) -> Result<Vec<Vec<T>>, Box<Error>>
    where
        T: FromStr,
        T::Err: 'static + Error,
    {
        (0..n).map(|_| read_line()).collect()
    }
}

fn power_modulo(m: u64, n: u64, c: u64) -> u64 {
    if n == 0 {
        return 1;
    }

    power_modulo(m * m % c, n / 2, c) * if n % 2 == 1 { m % c } else { 1 }
}

fn solve() -> Result<(), Box<std::error::Error>> {
    let header = utils::read_line::<u64>()?;
    let m = header[0];
    let n = header[1];

    println!("{}", power_modulo(m, n, 1_000_000_007));

    Ok(())
}

fn main() {
    match solve() {
        Err(err) => panic!("{}", err),
        _ => (),
    };
}

