题目描述

请注意，本题内存限制比通常题目更低。

有一条竖直的长条，共有 $n$ 个格子，从上到下编号为 $1$ 到 $n$。一个棋子初始位于格子 $n$，你需要通过若干次移动让它到达格子 $1$。

当棋子位于某个格子 $x>1$ 时，一次移动可以是下面两种之一：

• 减法移动：选择一个整数 $y$，满足 $1\le y\le x-1$，把棋子从 $x$ 移动到 $x-y$；
• 下取整除法移动：选择一个整数 $z$，满足 $2\le z\le x$，把棋子从 $x$ 移动到 $\left\lfloor\dfrac{x}{z}\right\rfloor$。

请计算用一次或多次移动从格子 $n$ 到达格子 $1$ 的方案数，并对 $m$ 取模。如果一次移动中有多种不同选择能到达同一个格子，这些选择也视为不同方案。

输入格式

一行两个整数 $n,m$，分别表示长条长度和模数。

输出格式

输出一个整数，表示从格子 $n$ 到格子 $1$ 的方案数，对 $m$ 取模。

样例

3 998244353

5

5 998244353

25

42 998244353

793019428

787788 100000007

94810539

说明

第一个样例中，从格子 $3$ 一步到达格子 $1$ 有 $3$ 种：减去 $y=2$，或者除以 $z=2$，或者除以 $z=3$。

另外还有 $2$ 种经过格子 $2$ 的方案：先减去 $y=1$，再减去 $y=1$ 或除以 $z=2$。

因此总方案数为 $5$。

数据范围

$2\le n\le4\times10^6$，$10^8<m<10^9$，且 $m$ 是质数。