#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<memory>
#include<bitset>
#include<utility>
#include<stdio.h>
#include<fstream>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=10000005;
unsigned int seed;
const unsigned int modo=998244353;
unsigned int get_rand()
{
    seed*=3;
    if (seed>=modo)
    {
        seed-=modo;
    }
    if (seed>=modo)
    {
        seed-=modo;
    }
    return seed;
}
unsigned int a[maxn];
unsigned int sum[maxn];
int main()
{
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>seed;
    if (seed>=modo)
    {
        seed-=modo;
    }
    if (seed>=modo)
    {
        seed-=modo;
    }
    if (seed>=modo)
    {
        seed-=modo;
    }
    if (seed>=modo)
    {
        seed-=modo;
    }
    int n,m;
    cin>>n>>m;
    int i;
    int q;
    cin>>q;
    sum[0]=0;
    for (i=0;i<n;i++)
    {
        a[i]=get_rand();
        sum[i+1]=sum[i]+a[i];
    }
    if (m*2<=n)
    {
        unsigned long long sumans=0;
        unsigned int l1=1,l2=0;
        unsigned int r1=0,r2=1;
        int cut1=m,cut2=n-m;
        for (i=0;i<q;i++)
        {
            int t=get_rand()%2;
            if (t==0)
            {
                register int l=get_rand()%n+1;
                register int r=get_rand()%n+1;
                if (l>r) swap(l,r);
                l--;
                register unsigned int query_ans=0;
                if (l<cut1)
                {
                    if (r<cut1)
                    {
                        query_ans+=(sum[r]-sum[l])*l1+(sum[cut2+r]-sum[cut2+l])*l2;
                    }
                    else
                    {
                        query_ans+=(sum[cut1]-sum[l])*l1+(sum[n]-sum[cut2+l])*l2;
                        if (r<cut2)
                        {
                            query_ans+=(sum[r]-sum[cut1]);
                        }
                        else
                        {
                            query_ans+=(sum[cut2]-sum[cut1]);
                            query_ans+=sum[r-cut2]*r1+(sum[r]-sum[cut2])*r2;
                        }
                    }
                }
                else
                {
                    if (l<cut2)
                    {
                        if (r<cut2)
                        {
                            query_ans+=(sum[r]-sum[l]);
                        }
                        else
                        {
                            query_ans+=(sum[cut2]-sum[l]);
                            query_ans+=sum[r-cut2]*r1+(sum[r]-sum[cut2])*r2;
                        }
                    }
                    else
                    {
                        query_ans+=(sum[r-cut2]-sum[l-cut2])*r1+(sum[r]-sum[l])*r2;
                    }
                }
                sumans+=query_ans;
            }
            else
            {
                t=get_rand()%2;
                if (t==0)
                {
                    l1+=r1;
                    l2+=r2;
                }
                else
                {
                    r1+=l1;
                    r2+=l2;
                }
            }
        }
        cout<<sumans<<endl;
    }
    else
    {
        unsigned long long sumans=0;
        unsigned int l1=1,l2=0;
        unsigned int r1=0,r2=1;
        unsigned int ll1=1,ll2=0,ll3=0;
        unsigned int mm1=0,mm2=1,mm3=0;
        unsigned int rr1=0,rr2=0,rr3=1;
        register int cut1=2*m-n,cut2=n-m,cut3=m,cut4=2*n-2*m;
        for (i=0;i<q;i++)
        {
            int t=get_rand()%2;
            if (t==0)
            {
                register int l=get_rand()%n+1;
                register int r=get_rand()%n+1;
                if (l>r) swap(l,r);
                l--;
                unsigned int query_ans=0;
                if (l<cut1)
                {
                    if (r<cut1)
                    {
                        query_ans+=(sum[r]-sum[l])*ll1+(sum[r+cut2]-sum[l+cut2])*ll2+(sum[r+cut4]-sum[l+cut4])*ll3;
                    }
                    else
                    {
                        query_ans+=(sum[cut1]-sum[l])*ll1+(sum[cut3]-sum[l+cut2])*ll2+(sum[n]-sum[l+cut4])*ll3;
                        if (r<cut2)
                        {
                            query_ans+=(sum[r]-sum[cut1])*l1+(sum[r+cut2]-sum[cut3])*l2;
                        }
                        else
                        {
                            query_ans+=(sum[cut2]-sum[cut1])*l1+(sum[cut4]-sum[cut3])*l2;
                            if (r<cut3)
                            {
                                query_ans+=sum[r-cut2]*mm1+(sum[r]-sum[cut2])*mm2+(sum[r+cut2]-sum[cut4])*mm3;
                            }
                            else
                            {
                                query_ans+=sum[cut1]*mm1+(sum[cut3]-sum[cut2])*mm2+(sum[n]-sum[cut4])*mm3;
                                if (r<cut4)
                                {
                                    query_ans+=(sum[r-cut2]-sum[cut1])*r1+(sum[r]-sum[cut3])*r2;
                                }
                                else
                                {
                                    query_ans+=(sum[cut2]-sum[cut1])*r1+(sum[cut4]-sum[cut3])*r2;
                                    query_ans+=sum[r-cut4]*rr1+(sum[r-cut2]-sum[cut2])*rr2+(sum[r]-sum[cut4])*rr3;
                                }
                            }
                        }
                    }
                }
                else if (l<cut2)
                {
                    if (r<cut2)
                    {
                        query_ans+=(sum[r]-sum[l])*l1+(sum[r+cut2]-sum[l+cut2])*l2;
                    }
                    else
                    {
                        query_ans+=(sum[cut2]-sum[l])*l1+(sum[cut4]-sum[l+cut2])*l2;
                        if (r<cut3)
                        {
                            query_ans+=sum[r-cut2]*mm1+(sum[r]-sum[cut2])*mm2+(sum[r+cut2]-sum[cut4])*mm3;
                        }
                        else
                        {
                            query_ans+=sum[cut1]*mm1+(sum[cut3]-sum[cut2])*mm2+(sum[n]-sum[cut4])*mm3;
                            if (r<cut4)
                            {
                                query_ans+=(sum[r-cut2]-sum[cut1])*r1+(sum[r]-sum[cut3])*r2;
                            }
                            else
                            {
                                query_ans+=(sum[cut2]-sum[cut1])*r1+(sum[cut4]-sum[cut3])*r2;
                                query_ans+=sum[r-cut4]*rr1+(sum[r-cut2]-sum[cut2])*rr2+(sum[r]-sum[cut4])*rr3;
                            }
                        }
                    }
                }
                else if (l<cut3)
                {
                    if (r<cut3)
                    {
                        query_ans+=(sum[r-cut2]-sum[l-cut2])*mm1+(sum[r]-sum[l])*mm2+(sum[r+cut2]-sum[l+cut2])*mm3;
                    }
                    else
                    {
                        query_ans+=(sum[cut1]-sum[l-cut2])*mm1+(sum[cut3]-sum[l])*mm2+(sum[n]-sum[l+cut2])*mm3;
                        if (r<cut4)
                        {
                            query_ans+=(sum[r-cut2]-sum[cut1])*r1+(sum[r]-sum[cut3])*r2;
                        }
                        else
                        {
                            query_ans+=(sum[cut2]-sum[cut1])*r1+(sum[cut4]-sum[cut3])*r2;
                            query_ans+=sum[r-cut4]*rr1+(sum[r-cut2]-sum[cut2])*rr2+(sum[r]-sum[cut4])*rr3;
                        }
                    }
                }
                else if (l<cut4)
                {
                    if (r<cut4)
                    {
                        query_ans+=(sum[r-cut2]-sum[l-cut2])*r1+(sum[r]-sum[l])*r2;
                    }
                    else
                    {
                        query_ans+=(sum[cut2]-sum[l-cut2])*r1+(sum[cut4]-sum[l])*r2;
                        query_ans+=(sum[r-cut4])*rr1+(sum[r-cut2]-sum[cut2])*rr2+(sum[r]-sum[cut4])*rr3;
                    }
                }
                else
                {
                    query_ans+=(sum[r-cut4]-sum[l-cut4])*rr1+(sum[r-cut2]-sum[l-cut2])*rr2+(sum[r]-sum[l])*rr3;
                }
                sumans+=query_ans;
            }
            else
            {
                t=get_rand()%2;
                if (t==0)
                {
                    l1+=r1;
                    l2+=r2;
                    ll1+=mm1;
                    ll2+=mm2;
                    ll3+=mm3;
                    mm1+=rr1;
                    mm2+=rr2;
                    mm3+=rr3;
                }
                else
                {
                    r1+=l1;
                    r2+=l2;
                    rr1+=mm1;
                    rr2+=mm2;
                    rr3+=mm3;
                    mm1+=ll1;
                    mm2+=ll2;
                    mm3+=ll3;
                }
            }
        }
        cout<<sumans<<endl;
    }
    return 0;
}