Pure Memory

Background

$\texttt{An intense dissatisfaction with the world.}$

$\texttt{And a compulsion to do something about it.}$

$\color{#1f1e33}\texttt{Heaven and Earth.}$

$\color{Gold}\texttt{My Guiding Star.}$

Description

形式化的讲，$awa$ 需要你求出

$$\sum\limits_{i=1}^{n}f(A(i, p)) \bmod 998244353$$

的值，其中，$A(i)$ 为数列。

对于 $f(A)$，有

$$f(A)=\max \{r - l + 1\}$$

其中的 $l,r$ 满足

$$\forall\ i \in [l + 1, r - 1], a_{i-1} + a_{i+1}=2a_i $$

对于长度为 $\left\lfloor\log_{p}{n}+1\right\rfloor$ 的整数数列 $A(n, p)$，有

$$a_i=\left\lfloor\dfrac{n\bmod p^i}{p^{i-1}}\right\rfloor $$

Sample Input & Output

读入一行 $n,p$。

输出一行，见简化题意。

5 3

8

998244353 19

131122467

98 10

187

1145141919810 60

302077622

Data Range

对于 $30\%$ 的数据，$n\leq10^6, p=60$；

对于 $60\%$ 的数据，$2\leq p \leq 20, n\leq p ^{10}$；

对于另外 $10\%$ 的数据，$p=10,1\leq n \leq 10^{18}$；

对于 $100\%$ 的数据，$2\leq p \leq 60, 1\leq n \leq p ^{18}$。

Tips

1. 请注意到本题 并不正常 的空间限制。
2. 仅保证时间限制在 std 的 $5$ 倍以上（卡常后）。
3. 如果需要，请使用：#pragma GCC optimize(2) 于代码第一行。