#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
int a[10000010],p[10000010];
int mid;
LL ans,qp=19;
priority_queue <int> q1,q2;
int main(){
    scanf("%d%d",&n,&a[0]);
    for(int i=1;i<=n;++i)   p[i]=i;
    for(int i=1;i<=n;++i)   a[i]=(1ll*a[i-1]*998244353+1000000007)%1000000009;
    for(int i=1;i<=n;++i)   swap(p[i],p[a[i]%i+1]);
    mid=p[1];
    ans=mid*19%998244353;
    for(int i=2;i<=n;++i){
        qp=qp*19%998244353;
        if(i&1){
            if(p[i]>-q2.top())   q2.push(-p[i]),mid=-q2.top(),q2.pop();
            else if(p[i]>q1.top())  mid=p[i];
            else q1.push(p[i]),mid=q1.top(),q1.pop();
            ans=(1ll*ans+mid*qp%998244353)%998244353;
        }
        else{
            if(p[i]>mid)    q2.push(-p[i]),q1.push(mid);
            else q1.push(p[i]),q2.push(-mid);
            ans=(1ll*ans+q1.top()*qp%998244353)%998244353;
        }
    }
    printf("%lld",ans);
    system("pause");
}