Matching In Multiplication

그래프 이론에서 이분 그래프는 정점 집합을 두 개의 서로소인 집합 $U$와 $V$로 나누어 모든 간선이 $U$의 어떤 정점과 $V$의 어떤 정점을 연결하도록 할 수 있는 무방향 그래프이다. $U$와 $V$는 각각 독립 집합이며, 보통 그래프의 두 부분이라고 부른다. 같은 조건을 달리 표현하면, 이분 그래프는 홀수 길이의 사이클을 포함하지 않는 그래프이다. 그래프의 매칭은 서로 정점을 공유하지 않는 간선들의 집합이다. 완전 매칭은 모든 정점이 매칭에 포함된 간선 하나로 덮이는 매칭이다.

Little Q는 이분 그래프의 정의를 잘못 이해했다. 그는 $U$의 크기와 $V$의 크기가 같고, $U$의 각 정점 $p$에서 나가는 간선이 정확히 두 개라고 생각한다. 이런 가중 그래프에서 그는 완전 매칭의 가중치를 매칭에 포함된 모든 간선의 가중치의 곱으로 정의하고, 그래프의 가중치를 모든 완전 매칭의 가중치의 합으로 정의한다.

Little Q가 만든 가중 그래프의 가중치를 계산하는 프로그램을 작성하시오.

첫째 줄에는 $U$의 크기를 나타내는 정수 $n$이 주어진다 ($1 \leq n\leq 3 \cdot 10^5$). $U$와 $V$의 정점은 각각 정수 $1, 2, \ldots, n$으로 번호가 붙는다.

다음 $n$개의 줄 중 $i$번째 줄에는 네 개의 정수 $v_{i, 1}$, $w_{i, 1}$, $v_{i, 2}$, $w_{i, 2}$가 주어진다. 이는 $U_i$와 $V_{v_{i, 1}}$ 사이에 가중치 $w_{i, 1}$인 간선이 있고, $U_i$와 $V_{v_{i, 2}}$ 사이에 가중치 $w_{i, 2}$인 간선이 있다는 뜻이다 ($1 \leq v_{i, j} \leq n$, $1 \leq w_{i, j} \leq 10^9$).

주어진 그래프에는 완전 매칭이 적어도 하나 있고, 모든 정점 쌍 사이에는 간선이 최대 하나만 존재한다.

주어진 그래프의 가중치를 나타내는 정수 하나를 한 줄에 출력한다. 답이 매우 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다.