AT_agc025_b [AGC025B] RGB Coloring

高桥君有一座塔，这座塔由 $N$ 个方块垂直堆叠而成。起初，所有方块都是无色的，但高桥君打算将其中一些方块涂成红色、绿色或蓝色中的一种颜色，以使塔变得美丽。高桥君将“塔的美丽度”定义如下： - 每个方块的得分为：若被涂成红色，则得 $A$ 分；若被涂成绿色，则得 $A+B$ 分；若被涂成蓝色，则得 $B$ 分；若无色，则得 $0$ 分。塔的美丽度即 $N$ 个方块得分的总和。 其中，$A,B$ 是给定的正整数常数，且每个方块不能同时被涂成两种或以上的颜色。 高桥君希望通过涂色，使塔的美丽度恰好等于 $K$。请问有多少种不同的涂色方法？请输出方案数对 $998244353$ 取模的结果。 如果存在某个方块，在两种方案中该方块的颜色不同，或者一个方案中该方块被涂色而另一个方案中该方块无色，则这两种方案被认为是不同的。

输入为一行，包含四个整数： > $N\ A\ B\ K$

输出使塔的美丽度恰好为 $K$ 的涂色方法数，对 $998244353$ 取模。

## 限制条件 - $1 \leq N \leq 3 \times 10^5$ - $1 \leq A,B \leq 3 \times 10^5$ - $0 \leq K \leq 18 \times 10^{10}$ - 输入的所有值均为整数 ## 样例解释 1 在本例中，红色每个得 $1$ 分，绿色每个得 $3$ 分，蓝色每个得 $2$ 分。美丽度为 $5$ 的情况有： - 1 个绿色，1 个蓝色 - 1 个红色，2 个蓝色 - 2 个红色，1 个绿色 - 3 个红色，1 个蓝色 因此，答案为 $40$。 ## 样例解释 2 美丽度为 $0$ 的塔只有所有方块都无色这一种情况。因此，答案为 $1$。 由 ChatGPT 4.1 翻译