题目描述

高桥有一个塔，分为 $N$ 层。初始时，所有的层都没有上色。高桥打算用红色、绿色或蓝色来粉饰塔顶，使其成为一座美丽的塔。他将“塔的美丽度”定义如下：

• 塔的美丽度是 $N$ 层中各层得分的总和，其中每层的得分如下所示：如果该层上色为红色，则得分为 $A$；如果该层上色为绿色，则得分为 $A+B$；如果该层上色为蓝色，则得分为 $B$；如果该层没有上色，则得分为 $0$。

这里，$A$ 和 $B$ 是事先给定的正整数。注意，一层不能同时被涂上两种或更多种颜色。

高桥计划为塔涂色，使塔的美丽度恰好为 $K$。有多少种不同的涂色方法？将计数结果模 $998244353$ 输出。

约束条件

• $1 ≤ N ≤ 3×10^5$
• $1 ≤ A,B ≤ 3×10^5$
• $0 ≤ K ≤ 18×10^{10}$
• 输入中的所有值都是整数。

输入格式

从标准输入读入数据，格式如下：

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

输出格式

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

示例输入 1

4 1 2 5

示例输出 1

40

在这种情况下，一个红色层价值 $1$ 分，一层绿色层价值 $3$ 分，蓝色层价值 $2$ 分。当塔顶采用以下涂色方案之一时，塔的美丽度为 $5$：

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

共有 $40$ 种不同的方案。

示例输入 2

2 5 6 0

示例输出 2

1

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

示例输入 3

90081 33447 90629 6391049189

示例输出 3

577742975