7503: Expectation

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:4 通过:4

题目描述

You are given an undirected graph consisting of n vertices with m weighted edges. We define the weight of a spanning tree as the bitwise AND of all edges' weight in spanning tree.

Now select a spanning tree randomly, you should calculate the expected value of the weight of this spanning tree. You are required to print the result mod 998244353. i.e., print x×y−1 mod 998244353 where x×y−1 is the irreducible fraction representation of the result, where y−1 denotes the multiplicative inverse of y modulo 998244353.

输入格式

The first line is an integer t(1≤t≤10), the number of test cases.

For each test case, there are two space-separated integers n(2≤n≤100) and m(1≤m≤104) in the first line, the number of nodes and the number of edges.

Then follows m lines, each contains three integers u,v,w(1≤u,v,≤n,1≤w≤109,u≠v), space separated, denoting an weight edge between u and v has weight w.

输出格式

For each test case, output a single line with a single integer, denoting the answer.

输入样例 复制

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

输出样例 复制

1