Broken Dream

Problem Description

People comfort and hug each other along the way, where they struggles desperately to chasing their broken and dying dream, which has long been an old friend of them, since the good old days. So does Akura. His dream is also broken now, and he wanted to make it reunited so that he can finally achieve it. From his perspective, his dream has already broken into several islands in the ocean, and there are bridges between some pair of islands, and every bridge has its own length. Akura's task is to find some bridges that connect all these islands, while minimizing the total length of the chosen bridges. However, not every bridge is available, there are possibilities that some bridges are broken. So he wants you to help him find the expectation of the total length of bridges you have to chosen so that all islands are connected. If in some situations there were no such selection to do so, you don't need to choose any bridges. Formally speaking, there are n islands and m bridges. The $i-$th bridge connects the $u_i-$th and $v_i-$th island, and has the length of $w_i$ and the possibility of $p_i$ that the bridge is $\bf{available}$. Your task is to find the expectation of total length of the bridges in the $\text{MST}$(minimum spanning tree) modulo $mod=998244353$. Note that if in some situations there is no $\text{MST}$ in the graph, we consider the total length of bridges in $\text{MST}$ is $0$.

Input

The input consists of multiple test cases. The first line contains a single integer $T(1\leq T\leq 7)$ --- the number of test cases. The first line of each test case contains $2$ integers $n,m(n\leq 15, m\leq 50)$. The following are $m$ lines. The $i-$th line contains $4$ integers $u_i,v_i,w_i,p_i\ (1\leq u_i,v_i\leq n, 0\leq w_i<998244353,2\leq p_i<998244353)$, where $p_i$ is the possibility modulo $998244353$.

Output

An interger, the expectation modulo $998244353$.

Sample Input

1
3 3
1 2 1 499122177
2 3 2 332748118
3 1 1 499122177

Sample Output

1

Source

2023“钉耙编程”中国大学生算法设计超级联赛（9）