var P = 2L

fun mod(x: Long) = if (x >= 0) x % P else (P - ((-x) % P)) % P
fun modPlus(x1: Long, x2: Long) = (x1 + x2) % P
fun modMinus(x1: Long, x2: Long) = (x1 + P - x2) % P
fun modTimes(x1: Long, x2: Long) = (x1 * x2) % P

fun main(args: Array<String>) {
  val (n, pInt) = readLine()!!.split(" ").map { it.toInt() }
  P = pInt.toLong()

  val pTable = LongArray(n + 1, { 0 })
  pTable[0] = 2L
  for (i in 1..n) {
    pTable[i] = modTimes(pTable[i - 1], pTable[i - 1])
  }

  val cTable = Array(n + 1, { LongArray(n + 1, { 0L })})
  cTable[0][0] = 1L
  for (i in 1..n) {
    for (j in 0..i) {
      cTable[i][j] = if (j == 0) 1L else modPlus(cTable[i - 1][j - 1], cTable[i - 1][j])
    }
  }

  val gTable = Array(n + 1, { LongArray(n + 1, { 0 })})
  gTable[0][0] = 1
  for (i in 1..n) {
    for (j in 0..i) {
      gTable[i][j] =
          if (j == 0 || j == i) 1
          else modPlus(gTable[i - 1][j - 1], modTimes(gTable[i - 1][j], (j + 1).toLong()))
    }
  }
//  println("gTable[2][0]" + gTable[2][0])
//  println("gTable[2][1]" + gTable[2][1])
//  println("gTable[2][2]" + gTable[2][2])
//  println("gTable[3][1]" + gTable[3][1])
//  println("gTable[4][2]" + gTable[4][2])

  val hTable = Array(n + 1, { LongArray(n + 1, { 0 }) })
  for (i in 0..n) {
    for (j in 0..n) {
      hTable[i][j] =
          if (i == 0 || j == 0) 1
          else if (i == 1) modTimes(hTable[1][j - 1], 2)
          else modTimes(hTable[i - 1][j], hTable[1][j])
    }
  }


  val fTable = LongArray(n + 1, { 0 })
  for (i in 1..n) {
    var acc = 0L
    for (x in 0..i) {
      acc = modPlus(acc, modTimes(gTable[i][x], hTable[x][n - i]))
    }
    fTable[i] = modTimes(pTable[n - i], acc)
  }

  var ans = pTable[n]
  for (k in 1..n) {
    val sign = if (k % 2 == 0) 1 else mod(-1)
    ans = modPlus(ans, modTimes(modTimes(sign, cTable[n][k]), fTable[k]))
  }

  println(ans)
}