{"problem":{"name":"Flip Cards","description":{"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$ writt","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc291_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc291_d","tags":[],"sample_group":[["3\n1 2\n4 2\n3 4","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}$."],["4\n1 5\n2 6\n3 7\n4 8","16"],["8\n877914575 602436426\n861648772 623690081\n476190629 262703497\n971407775 628894325\n822804784 450968417\n161735902 822804784\n161735902 822804784\n822804784 161735902","48"]],"created_at":"2026-03-03 11:01:14"}}