有一个 $n\times m\times l$ 的立方体，立方体中每个格子上都有一个数，如果某个格子上的数比三维坐标至少有一维相同的其他格子上的数都要大的话，我们就称它是极大的。

现在将 $1\sim n\times m\times l$ 这 $n\times m\times l$ 个数等概率随机填入 $n\times m\times l$ 个格子（即任意数字出现在任意格子上的概率均相等），使得每个数恰出现一次，求恰有 $k$ 个极大的数的概率。答案对 $998244353$（一个质数）取模。

输入格式

输入包含多组数据。输入第一行包含一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行一组数据，包含 $4$ 个正整数 $n,m,l,k$，表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示答案对 $998244353$ 取模的余数。

可以证明，答案一定为有理数。设其为 $a/b$（$a$ 和 $b$ 为互质的正整数，数据保证 $b$ 不为 $998244353$ 的倍数），则你需要保证输出的数 $x$ 满足 $0\le x<998244353$ 且 $a\equiv bx(\mathrm{mod}998244353)$。可以证明这样的 $x$ 唯一存在。

样例一

input

5
1 1 1 1
2 2 2 1
7 8 9 3
123 456 789 1
1000 1000 1000 10

output

1
142606337
736950806
246172965
189652652

样例二

见样例数据下载。

限制与约定

对于$10\mathrm{\%}$的数据，$n,m\le 2$，$l\le 3$，$k=1$。

对于$30\mathrm{\%}$的数据，$n,m,l,k\le 12$。

对于$40\mathrm{\%}$的数据，$n,m,l\le 100$。

对于$50\mathrm{\%}$的数据，$n,m,l\le 1000$。

对于$60\mathrm{\%}$的数据，$n,m,l\le 100000$，其中有占全部数据$30\mathrm{\%}$的数据保证$k=1$。

对于$80\mathrm{\%}$的数据，$n,m,l\le 1000000$，其中有占全部数据$40\mathrm{\%}$的数据保证$k=1$。

对于 $100\mathrm{\%}$ 的数据，$1\le n,m,l\le 5000000$，$1\le k\le 100$，$1\le T\le 10$。

其中有 $50\mathrm{\%}$ 的数据保证 $k=1$。

时间限制: 5s 12s

空间限制: 512MB

下载

样例数据下载