Nothingnuo 准备举办一场 ICPC 训练营。他邀请了两位超级选手 Zayin 和 dafeng 来出题，并要求他们同时进行讲座。由于题目价格昂贵，Nothingnuo 只能从他们那里购买 $n$ 套题目。每套题目仅用于一场比赛。这 $n$ 套题目必须分配给两个分部（divA 和 divB），且两个分部不能共享题目。也就是说，如果 divA 使用 $x$ 套题目举办 $x$ 场比赛，那么 divB 将使用剩余的 $(n - x)$ 套题目举办 $(n - x)$ 场比赛。

训练营的学生被分为 divA 和 divB。在训练营的开幕式上，两个分部的学生能量水平均为 0。

在每个单位时间内，每位老师有两种活动选择： 1. 进行一场讲座，之后学生的能量水平增加 1。 2. 使用最初分配的一套题目组织一场比赛，之后学生的能量水平减少 $m$。

一旦训练营开始（开幕后至少一个单位时间），学生的能量水平必须始终保持大于 0，否则他们会因为过度疲劳而不再参加课程或测试。

Zayin 负责 divA，dafeng 负责 divB。他们都有很多技术想要分享，因此都希望延长教学时间，但学生们不想太累，因为他们计划在训练营结束后去旅游。因此，Nothingnuo 要求训练营结束后 divA 学生的能量水平恰好为 $r$，而 divB 的能量水平恰好为 $s$。

Zayin 想知道训练营有多少种不同的日程安排。我们将一个特定分部的日程定义为按时间顺序排列的活动序列。我们将训练营的日程定义为两个分部活动序列的有序对。对于两个训练营日程，我们认为它们相同，当且仅当 divA 在两个日程中的活动序列相同，且 divB 的活动序列也相同（如果两个活动都是讲座或都是比赛，则认为它们相同。也就是说，我们忽略题目集之间的差异）。例如： 日程 1：Div.A (讲座, 讲座, 讲座, 比赛), Div.B (讲座, 比赛, 讲座, 讲座)。 日程 2：Div.A (讲座, 讲座, 比赛, 讲座), Div.B (讲座, 比赛, 讲座, 讲座)。 这两个日程是不同的。但如果我们把日程 2 中 Div.A 的序列改为 (讲座, 讲座, 讲座, 比赛)，那么它将与第一个日程相同。

输入格式

第一行包含一个整数 $T(1 \le T \le 10^4)$，表示测试用例的数量。 每个测试用例包含一行，包含四个整数 $n, m, r, s$，其中 $n$ 是题目集的数量，$m$ 是每套题目的体力消耗，$r$ 是训练营结束后 divA 的剩余体力，$s$ 是训练营结束后 divB 的剩余体力。$(1 \le n, m \le 10^7, n \times m \le 10^7, 1 \le r, s \le 5 \times 10^6)$

输出格式

对于每个测试用例，输出一行一个整数，表示不同训练营日程的数量。由于结果可能非常大，你只需要输出答案对 998244353 取模的结果。

样例

输入 1

2
3 2 1 2
4 1 1 1

输出 1

55
42

说明

对于第一个样例： 当 div.A 分配到 0, 1, 2, 3 套题目时，日程数量分别为 1, 1, 3, 12。 当 div.B 分配到 3, 2, 1, 0 套题目时，日程数量分别为 30, 7, 2, 1。 因此，不同日程的总数为 $1 \times 30 + 1 \times 7 + 3 \times 2 + 12 \times 1 = 55$。