AT_arc221_b [ARC221B] Two-Powered Sum

You are given a positive integer $ N $ and a prime $ P $ . There is a length- $ N $ sequence $ A=(A_1,A_2,\ldots,A_N) $ where all elements are $ 0 $ . You can repeat the following operation any number of times, possibly zero: - Choose a non-empty subset $ S $ of $ \lbrace 1,2,\ldots,N\rbrace $ . Let $ \displaystyle x=\sum_{i\in S}2^{i-1} $ . For each $ i\in S $ , replace $ A_i $ with $ x $ . Find the number, modulo $ P $ , of possible sequences $ A $ after repeating the operations.

The input is given from Standard Input in the following format: > $ N $ $ P $

Output the answer.

### Sample Explanation 1 The possible sequences $ A $ are $ (0),(1) $ , giving two possibilities. ### Sample Explanation 2 The possible sequences $ A $ are $ (0,0),(0,2),(1,0),(1,2),(1,3),(3,2),(3,3) $ , giving seven possibilities. ### Constraints - $ 1\leq N\leq 700 $ - $ P $ is a prime satisfying $ 10^8\lt P\lt 10^9 $ . - All input values are integers.