macro_rules !read_value {($iter :expr ,($($t :tt ) ,*) ) =>{($(read_value !($iter ,$t ) ) ,*) } ;($iter :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |read_value !($iter ,$t ) ) .collect ::<Vec <_ >>() } ;($iter :expr ,{chars :$base :expr } ) =>{read_value !($iter ,String ) .chars () .map (|c |(c as u8 -$base as u8 ) as usize ) .collect ::<Vec <usize >>() } ;($iter :expr ,{char :$base :expr } ) =>{read_value !($iter ,{chars :$base } ) [0 ] } ;($iter :expr ,chars ) =>{read_value !($iter ,String ) .chars () .collect ::<Vec <char >>() } ;($iter :expr ,char ) =>{read_value !($iter ,chars ) [0 ] } ;($iter :expr ,usize1 ) =>{read_value !($iter ,usize ) -1 } ;($iter :expr ,$t :ty ) =>{$iter .next () .unwrap () .parse ::<$t >() .unwrap () } ;}
macro_rules !input_inner {($iter :expr ) =>{} ;($iter :expr ,) =>{} ;($iter :expr ,mut $var :ident :$t :tt $($r :tt ) *) =>{let mut $var =read_value !($iter ,$t ) ;input_inner !{$iter $($r ) *} } ;($iter :expr ,mut $var :ident $($r :tt ) *) =>{input_inner !{$iter ,mut $var :usize $($r ) *} } ;($iter :expr ,$var :ident :$t :tt $($r :tt ) *) =>{let $var =read_value !($iter ,$t ) ;input_inner !{$iter $($r ) *} } ;($iter :expr ,$var :ident $($r :tt ) *) =>{input_inner !{$iter ,$var :usize $($r ) *} } ;}
macro_rules !input {(source =$s :expr ,$($r :tt ) *) =>{let mut iter =$s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;(iter =$iter :ident ,$($r :tt ) *) =>{let s ={use std ::io ::Read ;let mut s =String ::new () ;std ::io ::stdin () .read_to_string (&mut s ) .unwrap () ;s } ;let mut $iter =s .split_whitespace () ;input_inner !{$iter ,$($r ) *} } ;($($r :tt ) *) =>{let s ={use std ::io ::Read ;let mut s =String ::new () ;std ::io ::stdin () .read_to_string (&mut s ) .unwrap () ;s } ;let mut iter =s .split_whitespace () ;input_inner !{iter ,$($r ) *} } ;}
static mut MODULO: u32 = 1_000_000_007;
#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash)]
pub struct AnyModu32 {
    x: u32,
}
impl AnyModu32 {
    #[inline]
    pub fn new(x: u32) -> Self {
        AnyModu32 {
            x: x % Self::get_modulo(),
        }
    }
    #[inline]
    pub fn new_unchecked(x: u32) -> Self {
        AnyModu32 { x: x }
    }
    #[inline]
    pub fn one() -> Self {
        Self::new_unchecked(1)
    }
    #[inline]
    pub fn zero() -> Self {
        Self::new_unchecked(0)
    }
    #[inline]
    pub fn get_modulo() -> u32 {
        unsafe { MODULO }
    }
    #[inline]
    pub fn set_modulo(m: u32) {
        unsafe {
            MODULO = m;
        }
    }
    #[inline]
    pub fn pow(mut self, mut y: usize) -> Self {
        let mut x = Self::one();
        while y > 0 {
            if y & 1 == 1 {
                x = x * self;
            }
            self = self * self;
            y >>= 1;
        }
        x
    }
    #[inline]
    pub fn inv(self) -> Self {
        let (mut x, mut s, mut t, mut u) = (1i64, self.x as i64, Self::get_modulo() as i64, 0i64);
        while t != 0 {
            let k = s / t;
            s -= k * t;
            std::mem::swap(&mut s, &mut t);
            x -= k * u;
            std::mem::swap(&mut x, &mut u);
        }
        x %= Self::get_modulo() as i64;
        if x < 0 {
            x += Self::get_modulo() as i64;
        }
        Self::new(x as u32)
    }
}
pub mod modu32_impl {
    use super::*;
    use std::fmt;
    use std::iter::{Product, Sum};
    use std::num::ParseIntError;
    use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
    use std::str::FromStr;
    impl From<u32> for AnyModu32 {
        #[inline]
        fn from(x: u32) -> Self {
            Self::new(x)
        }
    }
    impl From<u64> for AnyModu32 {
        #[inline]
        fn from(x: u64) -> Self {
            Self::new_unchecked((x % Self::get_modulo() as u64) as u32)
        }
    }
    impl Add for AnyModu32 {
        type Output = Self;
        #[inline]
        fn add(self, rhs: Self) -> Self::Output {
            let mut x = self.x + rhs.x;
            if x >= Self::get_modulo() {
                x -= Self::get_modulo();
            }
            Self::new_unchecked(x)
        }
    }
    impl Sub for AnyModu32 {
        type Output = Self;
        #[inline]
        fn sub(self, rhs: Self) -> Self::Output {
            if self.x < rhs.x {
                Self::new_unchecked(self.x + Self::get_modulo() - rhs.x)
            } else {
                Self::new_unchecked(self.x - rhs.x)
            }
        }
    }
    impl Mul for AnyModu32 {
        type Output = Self;
        #[inline]
        fn mul(self, rhs: Self) -> Self::Output {
            Self::new_unchecked((self.x as u64 * rhs.x as u64 % Self::get_modulo() as u64) as u32)
        }
    }
    impl Div for AnyModu32 {
        type Output = Self;
        #[inline]
        fn div(self, rhs: Self) -> Self::Output {
            self * rhs.inv()
        }
    }
    impl Neg for AnyModu32 {
        type Output = Self;
        #[inline]
        fn neg(self) -> Self::Output {
            if self.x == 0 {
                Self::zero()
            } else {
                Self::new_unchecked(Self::get_modulo() - self.x)
            }
        }
    }
    impl Sum for AnyModu32 {
        #[inline]
        fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::zero(), Add::add)
        }
    }
    impl Product for AnyModu32 {
        #[inline]
        fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
            iter.fold(Self::one(), Mul::mul)
        }
    }
    impl<'a> Sum<&'a AnyModu32> for AnyModu32 {
        #[inline]
        fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::zero(), Add::add)
        }
    }
    impl<'a> Product<&'a AnyModu32> for AnyModu32 {
        #[inline]
        fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
            iter.fold(Self::one(), Mul::mul)
        }
    }
    impl fmt::Display for AnyModu32 {
        fn fmt<'a>(&self, f: &mut fmt::Formatter<'a>) -> Result<(), fmt::Error> {
            write!(f, "{}", self.x)
        }
    }
    impl FromStr for AnyModu32 {
        type Err = ParseIntError;
        #[inline]
        fn from_str(s: &str) -> Result<Self, Self::Err> {
            s.parse::<u32>().map(Self::new_unchecked)
        }
    }
    macro_rules! modu32_ref_binop {
        ($imp :ident ,$method :ident ,$t :ty ) => {
            impl<'a> $imp<$t> for &'a $t {
                type Output = <$t as $imp<$t>>::Output;
                #[inline]
                fn $method(self, other: $t) -> <$t as $imp<$t>>::Output {
                    $imp::$method(*self, other)
                }
            }
            impl<'a> $imp<&'a $t> for $t {
                type Output = <$t as $imp<$t>>::Output;
                #[inline]
                fn $method(self, other: &'a $t) -> <$t as $imp<$t>>::Output {
                    $imp::$method(self, *other)
                }
            }
            impl<'a, 'b> $imp<&'b $t> for &'a $t {
                type Output = <$t as $imp<$t>>::Output;
                #[inline]
                fn $method(self, other: &'b $t) -> <$t as $imp<$t>>::Output {
                    $imp::$method(*self, *other)
                }
            }
        };
    }
    modu32_ref_binop!(Add, add, AnyModu32);
    modu32_ref_binop!(Sub, sub, AnyModu32);
    modu32_ref_binop!(Mul, mul, AnyModu32);
    modu32_ref_binop!(Div, div, AnyModu32);
    macro_rules! modu32_ref_unop {
        ($imp :ident ,$method :ident ,$t :ty ) => {
            impl<'a> $imp for &'a $t {
                type Output = <$t as $imp>::Output;
                #[inline]
                fn $method(self) -> <$t as $imp>::Output {
                    $imp::$method(*self)
                }
            }
        };
    }
    modu32_ref_unop!(Neg, neg, AnyModu32);
    macro_rules! modu32_ref_op_assign {
        ($imp :ident ,$method :ident ,$t :ty ,$fromimp :ident ,$frommethod :ident ) => {
            impl $imp<$t> for $t {
                #[inline]
                fn $method(&mut self, rhs: $t) {
                    *self = $fromimp::$frommethod(*self, rhs);
                }
            }
            impl<'a> $imp<&'a $t> for $t {
                #[inline]
                fn $method(&mut self, other: &'a $t) {
                    $imp::$method(self, *other);
                }
            }
        };
    }
    modu32_ref_op_assign!(AddAssign, add_assign, AnyModu32, Add, add);
    modu32_ref_op_assign!(SubAssign, sub_assign, AnyModu32, Sub, sub);
    modu32_ref_op_assign!(MulAssign, mul_assign, AnyModu32, Mul, mul);
    modu32_ref_op_assign!(DivAssign, div_assign, AnyModu32, Div, div);
}
#[derive(Clone, Debug)]
pub struct MemorizedFactorial {
    n: usize,
    fact: Vec<AnyModu32>,
    inv_fact: Vec<AnyModu32>,
}
impl MemorizedFactorial {
    pub fn new(max_n: usize) -> MemorizedFactorial {
        let mut fact = vec![AnyModu32::new(1); max_n + 1];
        let mut inv_fact = vec![AnyModu32::new(1); max_n + 1];
        for i in 1..(max_n + 1) {
            fact[i] = fact[i - 1] * AnyModu32::new(i as u32);
            inv_fact[i] = inv_fact[i - 1] / AnyModu32::new(i as u32);
        }
        MemorizedFactorial {
            n: max_n + 1,
            fact: fact,
            inv_fact: inv_fact,
        }
    }
    pub fn combination(&self, n: usize, r: usize) -> AnyModu32 {
        if r <= n {
            self.fact[n] * self.inv_fact[r] * self.inv_fact[n - r]
        } else {
            AnyModu32::new(0)
        }
    }
    pub fn permutation(&self, n: usize, r: usize) -> AnyModu32 {
        if r <= n {
            self.fact[n] * self.inv_fact[n - r]
        } else {
            AnyModu32::new(0)
        }
    }
    pub fn homogeneous_product(&self, n: usize, r: usize) -> AnyModu32 {
        if n != 0 && r != 0 {
            self.combination(n + r - 1, r)
        } else {
            AnyModu32::new(1)
        }
    }
}
fn main() {
    input! { n, m: u32 };
    AnyModu32::set_modulo(m);
    let fact = MemorizedFactorial::new(n);
    let mut dp = vec![vec![AnyModu32::zero(); n + 1]; n + 1];
    dp[0][0] = AnyModu32::one();
    let mut ans = AnyModu32::zero();
    for i in 0..n {
        for j in 0..n + 1 {
            let ni = i + 1;
            let nj = j + 1;
            let d = dp[i][j] * AnyModu32::new(nj as u32);
            dp[ni][j] += d;
            if j < n {
                let d = dp[i][j];
                dp[ni][nj] += d;
            }
        }
    }
    for i in 0..n + 1 {
        let mut c = AnyModu32::zero();
        for j in 0..i + 1 {
            c += dp[i][j] * AnyModu32::new_unchecked(2).pow((n - i) * j);
        }
        AnyModu32::set_modulo(m - 1);
        let x = AnyModu32::new_unchecked(2).pow(n - i).x as usize;
        AnyModu32::set_modulo(m);
        c *= AnyModu32::new_unchecked(2).pow(x);
        c *= fact.combination(n, i);
        if i % 2 == 0 {
            ans += c;
        } else {
            ans -= c;
        }
    }
    print!("{}", ans);
}


Measured memory_bytes: 41212