Migrated from Lutece 1749 二项式定理

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给出$n$和$k$，计算$\sum_{i=0}^{ \lfloor \frac{n}{k} \rfloor }\binom{n}{i \ast k}$

Input

输入包含两个整数$n，k. ( 1 \leq n \leq 10^{18} , 1 \leq k \leq 30000 或者 k = 262144)$.

Output

输出$1$行表示答案，只需输出其在$\text{mod } 998244353$意义下的值即可

Samples

6 3

22

Note

“玲珑杯”ACM比赛 Round #20

Resources

Prepared by xiper