说明

沉默是一位小的建筑师，他喜欢他的积木，使各种建筑物。现在他又有了新的问题。他要建立建设一个大小为2*2* N的积木，但他只有一种块大小为1* 1 * 2。现在，他想知道他有多少种方法可以兴建的他的积木。





输入

有几行输入。每行输入数据集。有两个整数N和P（1<= N <=10亿，1<P <= 1,000,000），在每个测试案例。输入EOF结束。





输出

对于每个测试用例，输出一个行包含一个整数，这是他可以修建的积木数量differentways。因为答案可能会非常大，你只需要输出对n取余数后的答案-Descr iption

Silence is a little architect, he likes to make all kinds of buildings with his building blocks. Now he has a new problem. He want to build a building of size 2* 2* n. But he only has one kind of block of size 1* 1* 2. Now he wants to know how many ways he can build the building.





Input

There are several lines in the input. Each line is a set of input data. There are two integers n and p (1 <= n <= 1,000,000,000, 1 < p <= 1,000,000) in each test case. The input is end with EOF.





Output

For each test case, output a single line contains one integer which is the number of differentways he can build the building. Because of the answer may be very large, you just need to output the answer mod p.