得分：$700$ 分

问题陈述

高桥有一个被分为 $N$ 层的塔。 最初，所有层都是未上色的。高桥打算将一些层涂成红色、绿色或蓝色，以使塔变得美丽。 他将塔的美丽定义如下：

• 塔的美丽是 $N$ 层的分数之和，其中如果某一层涂成红色，则分数为 $A$；如果涂成绿色，则分数为 $A+B$；如果涂成蓝色，则分数为 $B$；如果未上色，则分数为 $0$。

这里，$A$ 和 $B$ 是预先给定的正整数常量。还要注意，一层不能涂成两种或更多种颜色。

高桥计划为塔涂色，使得塔的美丽恰好为 $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}$
• 输入中的所有值都是整数。

输入

输入通过标准输入以以下格式给出：

$N$ $A$ $B$ $K$

输出

打印涂色的方法数量，结果对 $998244353$ 取模。

4 1 2 5

40

在这种情况下，一层红色的分数为 $1$，一层绿色的分数为 $3$，蓝色的分数为 $2$。当我们有以下涂色层组合之一时，塔的美丽为 $5$：

• $1$ 绿色，$1$ 蓝色
• $1$ 红色，$2$ 蓝色
• $2$ 红色，$1$ 绿色
• $3$ 红色，$1$ 蓝色

产生这些组合的总方法数量为 $40$。

2 5 6 0

1

只有当所有层都未上色时，塔的美丽才为 $0$。因此，答案是 $1$。

90081 33447 90629 6391049189

577742975