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.

见题面

见题面