package main

import (
	"fmt"
)

func main() {
	var n, m int
	if _, err := fmt.Scan(&n, &m); err != nil {
		return
	}

	if n == 1 {
		fmt.Println(1 % m)
		return
	}

	MOD := int64(m)

	R := make([]int64, n+1)
	SumM := make([]int64, 2*n+2)
	PrefSum := make([]int64, 2*n+2)

	pow2 := int64(2) % MOD

	for length := 1; length <= n; length++ {
		if length == 1 {
			R[1] = 1 % MOD
			SumM[2] = (SumM[2] + R[1]) % MOD
		} else if length == 2 {
			R[2] = 1 % MOD
			SumM[4] = (SumM[4] + R[2]) % MOD
		} else {
			R[length] = pow2
			pow2 = (pow2 * 2) % MOD

			for L := 1; L < length; L++ {
				K := length - 2*L - 1
				cur_S := int64(0)
				if K >= 1 {
					cur_S = (R[L] * PrefSum[K]) % MOD
				}
				R[length] = (R[length] - cur_S + MOD) % MOD
				SumM[length+L] = (SumM[length+L] + cur_S) % MOD
			}
			SumM[2*length] = (SumM[2*length] + R[length]) % MOD
		}

		PrefSum[length+1] = (PrefSum[length] + SumM[length+1]) % MOD
	}

	fmt.Println(R[n] % MOD)
}