该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐校长望着操场上一排 $1 \leq N \leq 3 \times 10^5$ 张无色的座椅，突然有了出题灵感。

每把椅子的得分为：若被涂成红色，则得 $A$ 分；若被涂成绿色，则得 $A+B$ 分；若被涂成蓝色，则得 $B$ 分；若无色，则得 0 分。

$0 < A,B \leq 3 \times 10^5$

通过涂色，椅子的总得分恰好等于 $K(\leq 18 \times 10^{10})$。请问有多少种不同的涂色方法？请输出方案数对 998244353 取模的结果。

Format

Input

一行四个自然数：

$N\ A\ B\ K$

Output

输出使总得分恰好为 $K$ 的涂色方法数，对 $998244353$ 取模。

Samples

4 1 2 3

20

Limitation

1s, 1024KiB for each test case.