题目描述
我们说一个长为 $m$ 的正整数序列 $[a_1,\dots,a_m]$ 是好的，当且仅当它满足以下性质：
- $m\ne 0$，也就是序列非空。
- $a_i>a_{i-1}\ (2\le i\le m)$，也就是序列严格递增。
- $1\le a_i\le n\ (1\le i\le m)$，也就是序列的元素都是 $\le n$ 的正整数。
- $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$。详细数据范围如下表。
| 测试点编号 | $n\le $ |
|---|---|
| $1$ | $5$ |
| $2$ | $10$ |
| $3$ | $100$ |
| $4$ | $500$ |
| $5$ | $2000$ |
| $6$ | $5000$ |
| $7$ | $5\times 10^4$ |
| $8$ | $2\times 10^5$ |
| $9,10$ | $10^6$ |
时间限制：$1\texttt{s}$
空间限制：$1024\texttt{MB}$