{"raw_statement":[{"iden":"problem statement","content":"$N$ cards, numbered $1$ through $N$, are arranged in a line. For each $i\\ (1\\leq i < N)$, card $i$ and card $(i+1)$ are adjacent to each other. Card $i$ has $A_i$ written on its front, and $B_i$ written on its back. Initially, all cards are face up.\nConsider flipping zero or more cards chosen from the $N$ cards. Among the $2^N$ ways to choose the cards to flip, find the number, modulo $998244353$, of such ways that:\n\n*   when the chosen cards are flipped, for every pair of adjacent cards, the integers written on their face-up sides are different."},{"iden":"constraints","content":"*   $1\\leq N \\leq 2\\times 10^5$\n*   $1\\leq A_i,B_i \\leq 10^9$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"3\n1 2\n4 2\n3 4"},{"iden":"sample output 1","content":"4\n\nLet $S$ be the set of card numbers to flip.\nFor example, when $S={2,3}$ is chosen, the integers written on their visible sides are $1,2$, and $4$, from card $1$ to card $3$, so it satisfies the condition.\nOn the other hand, when $S={3}$ is chosen, the integers written on their visible sides are $1,4$, and $4$, from card $1$ to card $3$, where the integers on card $2$ and card $3$ are the same, violating the condition.\nFour $S$ satisfy the conditions: ${},{1},{2}$, and ${2,3}$."},{"iden":"sample input 2","content":"4\n1 5\n2 6\n3 7\n4 8"},{"iden":"sample output 2","content":"16"},{"iden":"sample input 3","content":"8\n877914575 602436426\n861648772 623690081\n476190629 262703497\n971407775 628894325\n822804784 450968417\n161735902 822804784\n161735902 822804784\n822804784 161735902"},{"iden":"sample output 3","content":"48"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}