Background

我教愚人启蒙「智识」——阿那克萨戈拉斯

愿「理性」启蒙真理

Description

众所周知，阿那克萨戈拉斯不喜欢别人叫他那刻夏。

某天，那刻夏老师遇到了一个式子: $\sum\limits_{i=0}^{\lfloor \frac{n}{d} \rfloor}C_{n}^{di}k^{i}$。

他想知道这个式子在已知 $n, k, d$ 三个参数的情况下有没有快速计算的方法。

Format

Input

一行输入三个整数 $n, k, d (0 \le n \le 10^{1000}$, $2\le d\le 16$, $1 \le k \le 10^{8})$。

Output

一行输出一个整数，表示式子的计算结果对 $998244353$ 取模的值。

Samples

1 2 2

1

3 2 2

7