题目描述

Milk 想要为自己出的题在评测机上构造数据。

这道题的数据构造方法是这样的：在 $1 \sim n$ 中随便挑选几个数出来成为一个集合。很简单吧。

但是 Milk 出的题有一个非常奇怪的限制，也就是给出的集合中，不能出现一个数对 $(x,y)$，使得 $x=ky$ 或者 $x=k^py$。所以说构造一个合情合理的数据是非常难的。

但是 Milk 是一个很有责任心的人，他想要给把自己的题的数据出的更好。于是她把 $n,k,p$ 交给你，并问你能构造出多少种符合题目条件的数据？

因为各位都知道这是生活所迫，所以 Milk 好心地，让你求其对 $998244353$ 取模的值。

输入格式

一行三个整数 $n,k,p$，意义如上。

输出格式

一行一个整数，表示能够构造出的数据数对 $998244353$ 取模的值。

4 2 2

8

数据范围

• 对于前 $10 \%$ 的数据，$p=2$；
• 对于前 $30 \%$ 的数据，$n \leq 300$；
• 对于前 $60 \%$ 的数据，$n \leq 5 \times 10^6$；
• 对于 $100 \%$ 的数据，$2 \leq n \leq 10^{14}$，$2 \leq p \leq 10$，$2 \leq k \leq 50$。