#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
using i64 = long long;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    while (b) {
        if (b & 1) {
            res = res * a;
        }
        b >>= 1;
        a = a * a;
    }
    return res;
}

template<i64 P>
struct ModInt {
    i64 x;
    constexpr ModInt() : x{} {}
    constexpr ModInt(i64 x) : x{norm(x % P)} {}
    constexpr i64 norm(i64 x) const {
        if (x >= P) {
            x -= P;
        } else if (x < 0) {
            x += P;
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    constexpr ModInt operator-() const {
        ModInt res;
        res.x = norm(P - x);
        return res;
    }
    constexpr ModInt inv() const {
        return power(*this, P - 2);
    }
    constexpr ModInt operator+=(ModInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr ModInt operator-=(ModInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr ModInt operator*=(ModInt rhs) & {
        x = norm(x * rhs.x % P);
        return *this;
    }
    constexpr ModInt operator/=(ModInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr ModInt operator+(ModInt lhs, ModInt rhs) {
        ModInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr ModInt operator-(ModInt lhs, ModInt rhs) {
        ModInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr ModInt operator*(ModInt lhs, ModInt rhs) {
        ModInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr ModInt operator/(ModInt lhs, ModInt rhs) {
        ModInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr bool operator==(ModInt lhs, ModInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(ModInt lhs, ModInt rhs) {
        return lhs.val() != rhs.val();
    }
    friend constexpr istream &operator>>(istream &is, ModInt &a) {
        i64 v;
        is >> v;
        a = ModInt(v);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const ModInt &a) {
        return os << a.val();
    }
};

using mint = ModInt<998244353>;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class T>
using Set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T>
using Multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e7 + 5;
int n;
int a[N], p[N];
mint pw[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> a[0];
    for (int i = 1; i <= n; i++) {
        a[i] = (1LL * a[i - 1] * 998244353 + 1000000007) % 1000000009;
        p[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        swap(p[i], p[a[i] % i + 1]);
    }

    pw[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * 19;
    }

    mint ans = 0;
    Set<int> st;
    for (int i = 1; i <= n; i++) {
        st.insert(p[i]);
        ans += pw[i] * (*st.find_by_order((i + 1) / 2 - 1));
    }
    cout << ans << endl;
    return 0;
}