给定一个由 $N$ 个整数组成的序列 $S=((a_1,b_1),(a_2,b_2),\cdots,(a_N,b_N))$，并且 $S$ 的元素是不同的。 $S$ 的连续子序列 $S_l,r=((a_l,b_l),(a_l+1,b_l+1),...,(a_r,b_r))$ 有 $N×(N+1)/2$ 个可能。我们需要计算所有 $f(S_l,r)$ 的和，其中 $f(S_l,r)$ 是使 $S$ 的所有元素都包含在 $A$ 中所需的最小操作次数，$A$ 是如下定义的序列： $A = ((0,1),(1,0))$

具体而言，f(S_l,r) = （使得S_l,r的所有元素都包含在A中所需的最小操作次数）。

如果这样的操作不存在，$f(S_l,r) = 0$。

最后，将所得结果取模 $998244353$ 后输出。

输入格式

输入的第一行包含一个整数 $N$。

接下来的 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示序列 $S$ 中的元素。

输出格式

输出一个整数，表示取模 $998244353$ 后的答案。

数据范围

对于 $30\%$ 的数据，$2 <= N <= 5$； 对于 $100\%$ 的数据，$2 <= N <= 10^3,0 <= a_i,b_i <= 10^9$。

输入输出样例

输入样例：

2
0 1
1 0

输出样例：

3