fun Power(base:Long, exponent:Long, prime:Long):Long{
    return when(exponent){
        0L -> 1
        1L -> base % prime
        else -> Power(base, exponent / 2, prime).let{(it * it % prime) * Power(base, exponent % 2, prime)} % prime
    }
}
fun FMemo(n:Int, prime:Long):Array<Long>{
    val g = Array(n + 1, {Array(it + 1, {0L})})
    for (i in 0 .. n){
        g[i][0] = 1
        for (j in 1 until i){
            g[i][j] = (g[i - 1][j] * (j + 1) + g[i - 1][j - 1]) % prime
        }
        g[i][i] = 1
    }
    val p = Array(n + 1){2L}.apply {
        for (idx in 1 .. n){
            this[idx] = this[idx - 1].let{it * it % prime}
        }
    }

    return Array(n + 1, {i ->
        var res:Long = 0
        var base = Power(2, n - i.toLong(), prime)
        var power = 1L
        for (j in 0 .. i){
            res += power * g[i][j] % prime
            res %= prime
            power = power * base % prime
        }
        res * p[n - i] % prime
    })
}
fun main(args:Array<String>):Unit{
    val (n, m) = readLine()!!.split(' ').map(String::toInt)
    val combination = Array(n + 1, {0L}).apply{
        var res = 1L
        for (i in 0 .. n){
            this[i] = res
            res = res * (n - i) % m
            res = res * Power(i + 1L, m - 2L, m.toLong()) % m
        }
    }
    val f = FMemo(n.toInt(), m.toLong())
    println((0..n).map{i -> ((if (i % 2 == 0) 1 else (m - 1)) * combination[i] % m) * f[i] % m }.sum() % m)

}