Moonlit Ribbon Knots

Time limit: 2000 msMemory limit: 256 MB

Gats has $N$ distinguishable ribbon pieces. Ribbon $i$ has endpoint colors $A_i$ and $B_i$ . In its listed orientation, $A_i$ is on the left and $B_i$ is on the right.

Gats prepares one row of ribbons as follows:

He chooses a permutation of all $N$ ribbons uniformly at random.
Independently for every ribbon, he flips a fair coin. On heads, the ribbon keeps its listed orientation. On tails, its left and right endpoints are exchanged.

The permutation and all $N$ coin flips are mutually independent. A coin is still flipped when both endpoints of a ribbon have the same color.

At each of the $N-1$ gaps between consecutive ribbons, Gats makes a neat knot if the two touching endpoint colors are equal. Let $X$ be the total number of neat knots.

Compute the expected value of $X^2$ .

Input

The first line contains an integer $N$ ( $1 \le N \le 2 \times 10^5$ ), the number of ribbon pieces.

Each of the next $N$ lines contains two integers and (), the endpoint colors of ribbon in its listed orientation.

Output

Print the value of $\mathbb E[X^2]$ modulo $998244353$ .

More precisely, if $\mathbb E[X^2]=u/v$ for integers and with not divisible by , print Such an inverse always exists under the given constraints.

Samples

Sample 1

Input

2
1 1
1 2

Output

499122177

The single gap is neat with probability $1/2$ . Thus $\mathbb E[X^2]=1/2$ , whose required residue is $499122177$ .

Sample 2

Input

Output

Every touching endpoint has color , so all gaps are neat. Therefore .