题目描述

$n$ 维超立方体可看作由 $n-1$ 维超立方体沿垂直于它的所有的棱的方向平移得到的立体图形。 我们可以将点看作 $0$ 维超立方体，将直线看作 $1$ 维超立方体，将正方形看作 $2$ 维超立方体……依此类推。任何一个 $n$ 维超立方体 $(n>0)$ 都是由低维的超立方体元素组成的：它的 $n-1$ 维表面 是 $n-1$ 维的超立方体，它的 $n-2$ 维边缘是 $n-2$ 维的超立方体，它的 $n-3$ 维元素是 $n-3$ 维的超立方体……

小 E 对妹子的情意即为在他的定情信物—— $K$ 维超立方体中含有每一维的元素个数。

由于元素个数可能较大，只需要输出它所包含的每一维元素个数模 $p$ 后的异或和。

输入格式

一行两个整数 $K,p$。

输出格式

一个非负整数,表示小 E 的定情信物所包含的每一维元素个数模 $p$ 后的异或和。注意异或和可能会大于 $p$。

3 7

3

4 2333

33

12 7723

360

样例解释

对于样例 #1，一个三维超立方体含有 $8$ 个零维元素、$12$ 个一维元素、$6$ 个二维元素、$1$ 个三维

元素，模 $7$ 后分别为 $1,5,6,1$，异或和为 $1\operatorname{xor} 5\operatorname{xor}6\operatorname{xor}1=3$。

数据规模与约定

对于 $100\%$ 的数据，$1\leq K \leq 10^7$，$p$ 为 $10^9$ 内的素数。