题目描述

小 $Y$ 正在玩一种很新的国际象棋。

棋盘是一个 $n\times m$ 的网格，每个格子都可以放车。

每个车会攻击它同行或者同列的其他车。

但是小 $Y$ 喜欢挑战，所以他会选出一个集合 $S$，集合 $S$ 内部的格子不能放车。

为此，他会给出 $c$ 个不同坐标，第 $i$ 个坐标 $(x_i,y_i)$ ，它有 $p_i$ 的概率被选入 $S$ 中，$1-p_i$ 的概率不被选入。

你需要求出，有多少种不同的放置恰好 $k$ 个车的方案，使得任意两个棋子不会相互攻击。

输出方案数的期望值对 $998244353$ 取模的结果。

输入格式

多组数据。

先输入一个 $T$ 代表数据组数。

对于每一组数据：

第一行四个整数 $n,m,k,c$ 。

接下来 $c$ 行，每行一个三元组，代表 $(x_i,y_i,p_i)$ 。

输出格式

每一组数据一个整数代表答案

样例输入

3
3 3 2 4
3 2 499122177
2 1 499122177
2 2 499122177
1 2 499122177
1 1 1 1
1 1 499122177
1 3 1 2
1 1 499122177
1 3 499122177

样例输出

499122187
499122177
2

样例解释

$499122177\equiv \frac{1}{2}\pmod {998244353}$ 。

对于第三组数据，答案为 $\frac{1}{4}(1\times 3+2\times 2+1\times1)=2$ 。

数据规模

• $20\%$ ，$n,m\leq 20$
• $20\%$ ，$c=0$
• $20\%$ ，$c\leq 20$
• $20\%$ ，$c\leq 40$

$1\leq k,n,m\leq 10^{7}，1\le c\leq 60$，保证给出的 $c$ 个坐标互不相同。