B'Everyone was happy coding, until suddenly a power shortage happened and the best competitive programming site went down. Fortunately, a system administrator bought some new equipment recently, including some UPSs. Thus there are some servers that are still online, but we need all of them to be working in order to keep the round rated. Imagine the servers being a binary string s of length n . If the i -th server is online, then s_i = 1 , and s_i = 0 otherwise. A system administrator can do the following operation called electricity spread, that consists of the following phases: We call a binary string s of length n rated if we can turn on all servers (i.e. make s_i = 1 for 1 <= i <= n ) using the electricity spread operation any number of times (possibly, 0 ). Your task is to find the number of rated strings of length n modulo m . The first and only line contains two integers n and m ( 1 <= n <= 5000 , 10 <= m <= 10^9 ) -- the length of the string and the required module. Print a single integer -- the number of rated binary strings of length n . Since this number can be large, print it modulo m . In the first example, the only rated string is 11. So the answer is 1 . In the second example, the rated strings are: In the third sample, the rated strings are: '...