subset-problem

You are given a set of integers from 1 to N. Count the interesting pairs of (A, B) that satisfy the following conditions:

A and B are both subsets of the given set.
XOR(A) ≤ XOR(B)
A and B have no common elements.
XOR(A) is the bit-xor (^ in C++ and Java) results over all its elements (e.g. XOR({1, 3}) = 2). We define the XOR of an empty set to be 0 (XOR({}) = 0).

Note: The answer may be large so you only need to print its remainder by dividing with M.

Input Format

The first line contains two space-separated integers, N and M.

Constraints

In 20% test cases: 1 ≤ N ≤ 10 
In 50% test cases: 1 ≤ N ≤ 100 M=109+7 
In 100% test cases: 1 ≤ N ≤ 3000 1 ≤ M ≤ 109+7
Output Format

Print the answer on a single line.

SAMPLE INPUT
2 10

SAMPLE OUTPUT
5

Explanation

If A = {}, B could be {}, {1}, {2}, and {1, 2}. 
If A = {1}, B could be {2}. 
If A = {2}, there is no valid B.

Source: hackerearth | Difficulty: EASY


Solutions: