E-Kevin的抽奖黑幕_牛客练习赛114

时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

我给你们黑幕。
—— 氧气少年 Kevin

氧气少年组织了几轮抽奖活动。

有 $n$ 名同学连续参加氧气少年组织的 $m$ 轮抽奖活动，每轮抽奖活动的流程如下：

氧气少年从 $n$ 名同学中随机地选择 $k$ 名同学，给这 $k$ 名同学发奖品；
随后，氧气少年看到连续多次没得到奖品的同学后于心不忍，于是决定给他们"黑幕"，即：给这 $n$ 名同学中的连续 $d$ 轮（包含当前这一轮）没得到奖品的同学发奖品。

请求出这 $m$ 轮抽奖过后，氧气少年发出奖品总数的期望。

可以证明，答案可以表示成 $\frac{p}{q}$ 的形式。其中， $p\geq 0,q\geq 1,\gcd(p,q)=1,q\mod 998244353\neq 0$ 。因此你只需输出 $p\cdot q^{998244351}\mod 998244353$ 即可。

输入描述:

第一行包含一个整数 ，表示测试用例的组数。

对于每组测试用例：

仅输入一行，包含四个整数 。

输出描述:

对于每组测试用例：

仅输出一行，包含一个整数，表示答案。

示例1

输入

复制

4
1 1 1 1
2 2 1 1
2 2 1 2
1924 1125 719 72

输出

复制

说明

对于第三组测试用例：

用实数表示的答案是 。