题目描述

我们说一个长为 $m$ 的正整数序列 $[a_1,\dots,a_m]$ 是好的，当且仅当它满足以下性质：

1. $m\ne 0$，也就是序列非空。
2. $a_i>a_{i-1}\ (2\le i\le m)$，也就是序列严格递增。
3. $1\le a_i\le n\ (1\le i\le m)$，也就是序列的元素都是 $\le n$ 的正整数。
4. $a_i\operatorname{xor}a_{i+1}\operatorname{xor}a_{i+2}\ne 0\ (1\le i\le m-2)$，也就是序列任意连续三项异或和都不是 $0$。

给定 $n$，请你数一数总共有多少个不同的好的序列。两个序列不同，当且仅当它们长度不同或者长度相同但是某个位置上的数不同。答案对 $mod$ 取模。

输入格式

输入一行两个正整数 $n,mod$。

输出格式

输出一个非负整数表示答案。

样例输入输出

样例输入 1

1 123456789

样例输出 1

1

样例输入 2

2 100000000

样例输出 2

3

样例 2 解释

满足条件的序列有 $[1],[2],[1,2]$ 三种。

样例输入 3

3 666666666

样例输出 3

6

样例 3 解释

满足条件的序列有 $[1],[2],[3],[1,2],[2,3],[1,3]$ 六种。

样例输入 4

5 987654321

样例输出 4

26

样例输入 5

322 998244353

样例输出 5

782852421

数据范围

本题 $10$ 个测试点，每个测试点 $10$ 分。对于所有测试点，$1\le n\le 10^6$，$10^8\le mod\le 10^9$。详细数据范围如下表。

时间限制：$1\texttt{s}$

空间限制：$1024\texttt{MB}$