시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

## 문제

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$.

## 예제 입력 1

2
2 1 1 4
1 4 2 3


## 예제 출력 1

16
{"ft_lang_label":"__label__en","ft_lang_prob":0.9247106,"math_prob":0.9997111,"size":1979,"snap":"2020-24-2020-29","text_gpt3_token_len":602,"char_repetition_ratio":0.1372152,"word_repetition_ratio":0.005376344,"special_character_ratio":0.30722588,"punctuation_ratio":0.1040724,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99992204,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-07-11T23:38:41Z\",\"WARC-Record-ID\":\"<urn:uuid:07252c5a-1ee9-4917-bf77-e9578afe6d3a>\",\"Content-Length\":\"28538\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:f5c0cd61-9275-4a2c-8038-9d6d3ebde915>\",\"WARC-Concurrent-To\":\"<urn:uuid:6c5d1641-0dad-4285-9f67-6dea72fcf027>\",\"WARC-IP-Address\":\"52.192.126.234\",\"WARC-Target-URI\":\"https://www.acmicpc.net/problem/18962\",\"WARC-Payload-Digest\":\"sha1:FTGUB23Y53TKIUL5NRYHK4V3LORN7C7C\",\"WARC-Block-Digest\":\"sha1:PBQRNYJKLEZRM4S5FCS7P6P4NTA4GCII\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-29/CC-MAIN-2020-29_segments_1593657129257.81_warc_CC-MAIN-20200711224142-20200712014142-00335.warc.gz\"}"}