题目描述

在卡兰德拉的王室秘藏中，守护机关由一排神秘的符石组成，共有 $N$ 枚。每枚符石都是双面的——正面刻着数字 $A_i$，背面则刻着另一个数字 $B_i$。初始时，所有符石正面朝上。

年轻的守卫 dash 得知，只有按照特定方式翻转符石，才能解锁通往档案馆的秘门。具体要求如下：

• 可以任意选择若干（包括 $0$ 枚）符石翻面；
• 翻转之后，任意相邻的两个符石，其朝上的数字必须不相同。

你的任务是帮 dash 计算，有多少种合法的翻转方式可以满足这个条件。由于答案可能很大，请输出其对 $998244353$ 取余的结果。

输入格式

第一行为一个整数 $N$，表示符石数量。

接下来的 $N$ 行中，每行包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 枚符石正反两面的数字。

输出格式

输出一个整数，表示满足条件的翻转方案总数，对 $998244353$ 取余。

样例

3
1 2
4 2
3 4

4

解释 #1

四个方案满足条件： $\{\},\{1\},\{2\}$ 和 $\{2,3\}$ 。

数据范围

• $1\leq N \leq 2\times 10^5$
• $1\leq A_i,B_i \leq 10^9$