#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>;

const int N = 1e7 + 5;
int n;
int a[N], p[N];
mint pw[N];
priority_queue<int, vector<int>, less<int>> big;
priority_queue<int, vector<int>, greater<int>> small;

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;
    for (int i = 1; i <= n; i++) {
        if (big.empty() || p[i] < big.top()) {
            big.push(p[i]);
        } else {
            small.push(p[i]);
        }
        while (small.size() > big.size()) {
            big.push(small.top());
            small.pop();
        }
        while (big.size() > small.size() + 1) {
            small.push(big.top());
            big.pop();
        }
        ans += pw[i] * big.top();
    }
    cout << ans << endl;
    return 0;
}