extern crate core;

use std::fmt;
use std::cmp::{Ordering, min, max};
use std::fmt::{Display, Error, Formatter};
use std::f32::MAX;
use std::ops::{Add, Sub, Mul, Div, Neg, Index, IndexMut};
use std::collections::{BTreeMap, VecDeque, BinaryHeap};

fn show<T: Display>(vec: &Vec<T>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        print!("[{}", vec[0]);
        for i in 1 .. vec.len() {
            print!(", {}", vec[i]);
        }
        println!("]");
    }
}
fn show2<T: Display>(vec: &Vec<Vec<T>>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        for l in vec {
            show(l);
        }
    }
}
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! read_value{
    () => {
        read_line!().trim().parse().ok().unwrap()
    }
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
macro_rules! let_mut_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let mut $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
fn power2(n: usize, modulo: i64) -> i64 {
    match n {
        0 => 1,
        1 => 2,
        _ => {
            let r = power2(n / 2, modulo);
            r * r % modulo * power2(n % 2, modulo) % modulo
        }
    }
}
fn power(e: usize, base: i64, modulo: i64) -> i64 {
    match e {
        0 => 1,
        1 => base,
        _ => {
            let r = power(e / 2, base, modulo);
            r * r % modulo * power(e % 2, base, modulo) % modulo
        }
    }
}
fn main() {
    let_all!(n: usize, m: i64);
    let mut factorial = vec![1_i64; n + 1];
    let mut inverse_factorial = vec![1_i64; n + 1];
    for i in 2 .. factorial.len() {
        factorial[i] = (i as i64 * factorial[i - 1]) % m;
        inverse_factorial[i] = (m - m / i as i64) * inverse_factorial[(m % i as i64) as usize] % m;
    }
    for i in 2 .. inverse_factorial.len() {
        inverse_factorial[i] = inverse_factorial[i] * inverse_factorial[i - 1] % m;
    }
    let mut result = 0_i64;
    for r in 1 .. n {
        let b = n - r;
        let mut temp = 0_i64;
        for i in 0 .. b {
            let single = (m + power2(b - i, m) - 1) % m;
            temp += ((m + 1 - i as i64 % 2) * 2 - 1) % m * power(r, single, m) % m * factorial[b] % m * inverse_factorial[i] % m * inverse_factorial[b - i] % m;
            temp %= m;
        }
        result += factorial[n] * inverse_factorial[r] % m * inverse_factorial[b] % m * temp % m * power2(r * (r - 1) / 2, m) % m * power2(b * (b - 1) / 2, m) % m;
        result %= m;
    }
    println!("{}", result);
}


Measured memory_bytes: 5040