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.