题目描述

高桥君有一座塔，这座塔由 $N$ 个方块垂直堆叠而成。起初，所有方块都是无色的，但高桥君打算将其中一些方块涂成红色、绿色或蓝色中的一种颜色，以使塔变得美丽。高桥君将“塔的美丽度”定义如下：

• 每个方块的得分为：若被涂成红色，则得 $A$ 分；若被涂成绿色，则得 $A+B$ 分；若被涂成蓝色，则得 $B$ 分；若无色，则得 $0$ 分。塔的美丽度即 $N$ 个方块得分的总和。

其中，$A,B$ 是给定的正整数常数，且每个方块不能同时被涂成两种或以上的颜色。

高桥君希望通过涂色，使塔的美丽度恰好等于 $K$。请问有多少种不同的涂色方法？请输出方案数对 $998244353$ 取模的结果。

如果存在某个方块，在两种方案中该方块的颜色不同，或者一个方案中该方块被涂色而另一个方案中该方块无色，则这两种方案被认为是不同的。

输入格式

输入为一行，包含四个整数：

$N\ A\ B\ K$

输出格式

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

样例 1

输入

4 1 2 5

输出

40

样例 2

输入

2 5 6 0

输出

1

样例 3

输入

90081 33447 90629 6391049189

输出

577742975

说明/提示

限制条件

• $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 翻译