18962번 - Matching In Multiplication 다국어

문제

In the mathematical discipline of graph theory, a bipartite graph is an undirected graph whose vertices can be divided into two disjoint sets $U$ and $V$ such that every edge connects some vertex in $U$ to some vertex in $V$. The vertex sets $U$ and $V$ are both independent sets, and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. A matching in a graph is a set of edges without common vertices. A perfect matching is a matching such that each vertex is covered by an edge from the matching.

Little Q misunderstood the definition of bipartite graph. He thinks the size of $U$ is equal to the size of $V,ドル and for each vertex $p$ in $U,ドル there are exactly two edges from $p$. Based on such weighted graph, he defines the weight of a perfect matching as the product of weights of all the edges included in the matching, and the weight of a graph as the sum of all the perfect matchings' weights.

Your task is to write a program to compute the weight of a weighted graph made by Little Q.

입력

The first line of the input contains an integer $n$ denoting the size of $U$ (1ドル \leq n\leq 3 \cdot 10^5$). The vertices in $U$ and $V$ are labeled separately by the integers 1,ドル 2, \ldots, n$.

In the next $n$ lines, the $i$-th line contains four integers $v_{i, 1},ドル $w_{i, 1},ドル $v_{i, 2}$ and $w_{i, 2}$ which mean that there is an edge between $U_i$ and $V_{v_{i, 1}}$ with weight $w_{i, 1},ドル and there is another edge between $U_i$ and $V_{v_{i, 2}}$ with weight $w_{i, 2}$ (1ドル \leq v_{i, j} \leq n,ドル 1ドル \leq w_{i, j} \leq 10^9$).

It is guaranteed that the given graph has at least one perfect matching, and there is at most one edge between every pair of vertices.

출력

Print a single line containing a single integer: the weight of the given graph. Since the answer may be very large, print it modulo 998ドル,244円,353円$.

제한

힌트