use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn pow_mod(base: i64, power: i64, modulo: i64) -> i64 {
    let mut base = base;
    let mut power = power;
    let mut ans = 1;
    while power > 0 {
        if power & 1 == 1 {
            ans = ans * base % modulo;
        }
        power >>= 1;
        base = base * base % modulo;
    }
    ans
}

#[allow(dead_code)]
fn inv_mod(a: i64, modulo: i64) -> i64 {
    pow_mod(a, modulo - 2, modulo)
}

const FACT_MAX: usize = 100000;
static mut FACTORIAL: [i64; FACT_MAX + 1] = [0; FACT_MAX + 1];
static mut RFACTORIAL: [i64; FACT_MAX + 1] = [0; FACT_MAX + 1];
fn init_fact(modulo: i64) {
    unsafe {
        if FACTORIAL[0] == 0 {
            FACTORIAL[0] = 1;
            for i in 1..FACT_MAX + 1 {
                FACTORIAL[i] = (FACTORIAL[i - 1] * i as i64) % modulo;
            }
            RFACTORIAL[FACT_MAX] = inv_mod(FACTORIAL[FACT_MAX], modulo);
            for i in (0..FACT_MAX).rev() {
                RFACTORIAL[i] = RFACTORIAL[i + 1] * (i as i64 + 1) % modulo;
            }
        }
    }
}
#[allow(dead_code)]
fn fact(n: i64, modulo: i64) -> i64 {
    let n = n as usize;
    init_fact(modulo);
    unsafe { FACTORIAL[n] }
}
#[allow(dead_code)]
fn rfact(n: i64, modulo: i64) -> i64 {
    let n = n as usize;
    init_fact(modulo);
    unsafe { RFACTORIAL[n] }
}
#[allow(dead_code, unused_comparisons)]
fn combi(n: i64, m: i64, modulo: i64) -> i64 {
    if n < m || m < 0 {
        return 0;
    }
    let n = n as usize;
    let m = m as usize;
    init_fact(modulo);
    unsafe { FACTORIAL[n] * RFACTORIAL[m] % modulo * RFACTORIAL[n - m] % modulo }
}

// fn calc_inner(
//     memo: &mut Vec<Vec<i64>>,
//     modulo: i64,
//     v: usize,
//     rest: usize,
//     cnt: usize,
//     amp: i64,
// ) -> i64 {
//     println!("inner: {} {} {} {}", v, rest, cnt, amp);
//     let mut ret = calc(memo, modulo, v + 1, rest) * amp % modulo * rfact(cnt, modulo) % modulo;
//     println!("{} {} {}", ret, amp, rfact(cnt, modulo));
//     if v < rest {
//         let namp = (amp * combi(rest, v, modulo)) % modulo;
//         ret = (ret + calc_inner(memo, modulo, v, rest - v, cnt + 1, namp)) % modulo;
//     }
//     ret
// }

// fn calc(memo: &mut Vec<Vec<i64>>, modulo: i64, v: usize, rest: usize) -> i64 {
//     if v > rest {
//         return 1;
//     }
//     if memo[v][rest] != -1 {
//         return memo[v][rest];
//     }
//     let ret = calc_inner(memo, modulo, v, rest, 0, 1) % modulo;
//     memo[v][rest] = ret;
//     println!("{} {} {}", v, rest, ret);
//     ret
// }

struct Solver {
    n: i64,
    modulo: i64,
    memo2: Vec<Vec<i64>>,
}

impl Solver {
    fn new() -> Solver {
        let n: i64 = read();
        let modulo: i64 = read();
        Solver {
            n: n,
            modulo: modulo,
            memo2: vec![vec![-1; n as usize + 1]; n as usize + 1],
        }
    }

    fn calc2(&mut self, rest: i64, w: i64) -> i64 {
        if w < rest {
            return 0;
        }
        if rest == 0 {
            return 1;
        }
        if self.memo2[rest as usize][w as usize] != -1 {
            return self.memo2[rest as usize][w as usize];
        }
        let mut ret = self.calc2(rest, w - 1);
        ret = (ret + self.calc2(rest - 1, w - 1)) % self.modulo;
        ret = (ret + self.calc2(rest, w - 1) * rest) % self.modulo;
        self.memo2[rest as usize][w as usize] = ret;
        ret
    }
    fn calc(&mut self, w: i64) -> i64 {
        let modulo = self.modulo;
        let other = self.n - w;
        let mut ret = 0;
        for cnt in 0..w + 1 {
            ret = (ret + self.calc2(cnt, w) * pow_mod(2, other * cnt, modulo) % modulo) % modulo;
        }
        ret
    }
    fn solve(&mut self) -> i64 {
        let n = self.n;
        let modulo = self.modulo;
        let mut sum = 0;
        for i in 0..n + 1 {
            let target = self.calc(i) * combi(n, i, modulo) % modulo;
            let other = pow_mod(2, pow_mod(2, n - i, modulo - 1), modulo);
            let sign = if i % 2 == 0 { 1 } else { -1 };
            sum = (sum + target * other % modulo * sign + modulo) % modulo;
        }
        sum
    }
}

fn main() {
    let mut solver = Solver::new();
    let ans = solver.solve();
    println!("{}", ans);
}


Measured memory_bytes: 92028