Code

#include <bits/stdc++.h>
using namespace std;

const int face_up = 0;
const int face_down = 1;

const int mod = 998244353;

void add(int &a, int b) {
    a += b;
    a %= mod;
}

int solve(vector<int> &up, vector<int> &down) {
    int n = up.size();

    // dp[i][state] is the number of "valid" configurations of cards[0...i] in
    // which the i-th elements ends up in state "state".
    // Note:
    // 1. State can be one of "face_up" or "face_down".
    // 2. A valid configuration is one where no two adjacent elements are equal.
    vector<vector<int>> dp(n, vector<int>(2, 0));

    // Base case. When we have just one card, there's one way of arranging
    // it face up and one way of arranging it face down.
    dp[0][face_up] = 1;
    dp[0][face_down] = 1;

    for (int i = 1; i < n; i++) {
        // Case 1 : The state of i-1 and i^th card is : (face_up), (face_up)
        if (up[i - 1] != up[i]) {
            add(dp[i][face_up], dp[i - 1][face_up]);
        }

        // Case 2 : The state of i-1 and i^th card is : (face_down), (face_up)
        if (down[i - 1] != up[i]) {
            add(dp[i][face_up], dp[i - 1][face_down]);
        }

        // Case 3 : The state of i-1 and i^th card is : (face_up), (face_down)
        if (up[i - 1] != down[i]) {
            add(dp[i][face_down], dp[i - 1][face_up]);
        }

        // Case 4 : The state of i-1 and i^th card is : (face_down), (face_down)
        if (down[i - 1] != down[i]) {
            add(dp[i][face_down], dp[i - 1][face_down]);
        }
    }

    int ans = 0;
    add(ans, dp[n - 1][face_up]);
    add(ans, dp[n - 1][face_down]);

    return ans;
}

int main() {
    int n;
    cin >> n;

    vector<int> up(n), down(n);
    for (int i = 0; i < n; i++) {
        cin >> up[i] >> down[i];
    }

    int res = solve(up, down);
    cout << res << "\n";
}