#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
int mod = 998'244'353;
#define o_set tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define int long long
long long bin_pow(__int128 x, int pow) {
    if (pow == 0)return 1;
    if (pow % 2 == 1)return (x * bin_pow(x, pow - 1)) % mod;
    else {
        return bin_pow(x * x  % mod, pow / 2) % mod;
    }
}
signed main() {
    int n, q;
    cin >> n >> q;
    vector<int>a(n);
    for (int i = 0;i < n;i++)a[i]=i + 1;
    while (q--) {
        int t;
        cin >> t;
        vector<int>b(n);
        if (t == 1) {
            for (int i = 0;i < n;i++) {
                b[i] = a[n - i - 1];
            }
        }
        if (t == 2) {

            for (int i = 0;i < n;i++) {
                b[i] = n - a[i] +1 ;
            }
        }
        if (t == 3){

            for (int i = 0;i < n;i++) {
                b[a[i] - 1] = i + 1;
            }
        }
        long long ans = 0;
        swap(a, b);
        for (int i = 0;i < n;i++) {
            ans += bin_pow(a[i],  i + 1);
            ans %= mod;
        }
        cout << ans << endl;
    }
}