Matthew 已经为UOJ工作了很多年，出过很多令人耳目一新的妙题——但他仍然不怎么会写题面。

而这次为了准备 NOI 而举办的 UNR，由于人手不够，写题面的重担落到了 Matthew 的头上，可是学了八门语言的 Matthew 哪里会使用汉语写作呢，写出来的都是形如 “La main dans la main, nous vivrons ensemble jusqu'à la fin de la vie” 一般，令大多数人不明所以的东西，在绞尽脑汁写题面的过程中，Matthew 不小心睡着了……

Matthew 睡得很沉，还做了个梦，梦见自己来到了 OI 大帝的面前，向 OI 大帝讨教写题面的秘方。

OI 大帝用斯洛僧嘉高里西利斯克语告诉 Matthew，如果你能解出下面的问题，这写题面的秘方便告诉你：

给定参数 $b, c$，求满足以下条件的 $m$ 元组 $(x_1, x_2, \dots, x_m)$ 的方案数：

• $x_i \in \mathbb{Z}$，即每个 $x_i$ 都是整数
• $0 \leq x_i \leq b^i - c$
• $x_1 + x_2 + \dots + x_m < n$.

Matthew 冥思苦想了许久，终于一拍脑袋大叫一声：“我会啦！”

可是梦突然就醒了……

Matthew 茫然的看着电脑，这题面似乎就写好了呢？

那作为正在备战 NOI 的可怜的你，当然得解决 OI 大帝给出的问题啦！

当然，你只需要输出答案对 $998244353$ 取模的结果即可。

输入格式

第一行三个整数 $m,b,c$，第二行一个整数 $n$，含义均如前所述。

输出格式

一行一个整数表示答案对 $998244353$ 取模的结果。

样例一

input

2 2 1
3

output

5

explanation

Explication:

Les restrictions sont $x_1 \le 1, x_2 \le 3$.

Les solutions sont $\{0, 0\}, \{0, 1\}, \{0, 2\}, \{1, 0\}, \{1, 1\}$.

样例二

input

6 2 0
100

output

4705522

explanation

いいえコメントありません

样例三

input

50 50 0
5123021850918490285093289038490280918904289058934081194908904690941972871983

output

316279832

explanation

Bez komentarza

限制与约定

对于 $10\%$ 的数据，$m \le 3, c = 1$；

对于 $30\%$ 的数据，$m \le 15, c = 1$；

对于 $60\%$ 的数据，$c = 1$；

对于 $100\%$ 的数据，$c \in \{0, 1\}, 0 \leq n < b ^ {m + 1}, 2 \le b \le 50, 1 \le m \le 50$.

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载