Migrated from Lutece 2489 期望

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一个有 $n$ 个点 $m$ 条带权边的图。我们定义一个生成树的权值为所有边权的二进制按位与。

现在我们随机地在图中选取一棵生成树，要你计算这个生成树的权值的期望值，输出期望值 $\bmod\ 998244353$ 后的结果。

Input

第一行一个整数 $t\ (1 \leq t \leq 10)$，表示数据组数

对于每组数据，第一行两个整数 $n\ (2 \leq n \leq 100)$ 和 $m\ (1 \leq m \le 10^4)$，代表这组数据图的点数和边数。

接下来 $m$ 行每行三个整数 $u, v, w\ (1 \leq u, v \leq n, 1 \leq w \leq 10^9, u \neq v)$，表示一条从 $u$ 到 $v$ 的变权值为 $w$。

Output

对于每一组数据，输出一行表示在模 $998244353$ 的情况下，生成树权值的期望。

Samples

1
3 3
1 2 1
1 3 1
2 3 1

1

Resources

2021 UESTC ICPC Training for Graph