请注意,此问题中的内存限制低于其他问题。
您有一个包含 $$$n$$$ 单元格的垂直条,从上到下从 $$$1$$$ 到 $$$n$$$ 连续编号。
您还有一个最初放置在单元格 $$$n$$$ 中的令牌。您将向上移动令牌,直到它到达单元格$$$1$$$。
让令牌在某个时刻位于单元格 $$$x > 1$$$ 中。令牌的一次转变可以有以下类型之一:
- 减法:选择 $$$1$$$ 和 $$$x-1$$$(含)之间的整数 $$$y$$$,并将标记从单元格 $$$x$$$ 移动到单元格 $$$x - y$$$。
- 向下除法:选择 $$$2$$$ 和 $$$x$$$(含)之间的整数 $$$z$$$,并将标记从单元格 $$$x$$$ 移动到单元格 $$$\lfloor \frac{x}{z} \rfloor$$$ ($$$x$$$ 除以 $$$z$$$ 向下舍入)。
求出使用一个或多个移位将标记从单元格 $$$n$$$ 移动到单元格 $$$1$$$ 的方法数,并以 $$$m$$$ 为模打印它。请注意,如果有多种方法可以在一个班次中将令牌从一个单元格移动到另一个单元格,则所有这些方法都被认为是不同的(检查示例解释以更好地理解)。
输入
唯一一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 4 \cdot 10^6$$$; $$$10^8 < m < 10^9$$$; $$$m$$$ 是质数) — 条带的长度和模数。
输出
打印将令牌从单元格 $$$n$$$ 移动到单元格 $$$1$$$ 的方式数,以 $$$m$$$ 为模。
示例
输入 #1
3 998244353
输出 #1
5
输入 #2
5 998244353
输出 #2
25
输入 #3
42 998244353
输出 #3
793019428
输入#4
787788 100000007
输出#4
94810539
注意
在第一个测试中,可以通过三种方法在一个班次中将标记从单元格 $$$3$$$ 移动到单元格 $$$1$$$:使用减法 $$$y = 2$$$,或使用除以 $$$z = 2$$$ 或 $$$z = 3$$$。
还有两种方法可以通过单元格 $$$2$$$ 将令牌从单元格 $$$3$$$ 移动到单元格 $$$1$$$:首先减去 $$$y = 1$$$,然后再次减去 $$$y = 1$$$ 或除以 $$$z = 2$$$。
因此,一共有五种方式。