program test
implicit none

integer(8),parameter :: num = 3000
integer(8) :: n,m,i,j,k
integer(8) :: comb(0:num,0:num)=0
integer(8) :: s(0:num,0:num)=0,ways(0:num)=0,ways2(0:num,0:num)=0,ruijyou(0:num*num)=0
integer(8) :: ans=0,ans_all=0,ans_not=0,kuruchi=0

read(*,*) n,m

!コンビネーションの計算
comb(1,0) = 1
comb(1,1) = 1
do i=2,n
	comb(i,0) = 1
	do j=1,i
		comb(i,j) = comb(i-1,j-1) + comb(i-1,j)
	enddo
enddo

!累乗の計算をしておく
ruijyou(0) = 1
do i=1,n*n
	ruijyou(i) = mod(2*ruijyou(i-1),m)
enddo

!第2種スターリング数っぽいのをを求めておく
!s(1,0)は、1通り
!s(1,1)は、1通り？ {[A]}

!s(2,0)は、1通り
!s(2,1)は、{[A]},{[B]},{[A,B]}の3通り
!s(2,2)は、{[A][B]}の1通り

!s(3,0)は、1通り
!s(3,1)は、7通り
!s(3,2)は、 s(2,1) + 2*s(2,2) = 5通り
!s(3,3)は、 s(2,2) + 2*s(2,3) = 1通り


!{[A][C]},{[B][C]},{[A,B][C]} 新ラーメンに新しいトッピングを入れる
!{[A,C][B]},{[A][B,C]} 新トッピングを入れるラーメンを選ぶ


s(0:n,0) = 1

do i=1,n
	s(i,1) = ruijyou(i)-1
enddo

do i=2,n
	do j=2,i
		s(i,j) = mod(s(i-1,j-1) + j*s(i-1,j),m)
	enddo
enddo

!j個のラーメンのトッピングありについて、考慮しなかったi+1～Nの(N-i)個のトッピングについては
!不問にしていたので、2**((N-i)*j)倍する必要がある
!また、トッピングなしのラーメンの組み合わせは、n-i種類を自由に組み合わせた集合の
!2**(2**(n-i))種類あるので、

do i=1,n
	do j=0,i
		ways2(i,j) = mod(s(i,j) * ruijyou((n-i)*j),m)
		ways2(i,j) = mod(ways2(i,j) * ruijyou(ruijyou(n-i)),m)
	enddo
enddo

!i種類のトッピングがいずれも1杯以下にしか乗っていない個数
do i=1,n
	do j=0,i
		ways(i) = mod(ways(i) + ways2(i,j),m)
	enddo
enddo

!全てのラーメンの組み合わせ
	ans_all = ruijyou(ruijyou(n))

!求めていないものの組み合わせ
do i=1,n
	ans_not = mod(ans_not + comb(n,i)*ways(i) * (-1)**(i-1) , m)
	write(*,*) comb(n,i),ways(i)
enddo

ans = mod(ans_all - ans_not, m)
write(*,*) ans

end program