CodeForces_sqrtTree

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

long long mod;

typedef long long ll;

long long addMod(long long a, long long b){
    a += b;
    if(a >= mod)
        a -= mod;
    return a;
}

long long op(long long a, long long b){
    long long res = 0;
    a %= mod;
    while(b){
        if(b & 1LL) {
            res = addMod(res, a);
        }
        a = addMod(a, a);
        b /= 2;
    }
    return res;
}
inline int log2Up(int n) {
    int res = 0;
    while ((1 << res) < n) {
        res++;
    }
    return res;
}

class SqrtTree {
    private:
        int n, lg;
        vector<long long> v;
        vector<int> clz;
        vector<int> layers;
        vector<int> onLayer;
        vector< vector<long long> > pref;
        vector< vector<long long> > suf;
        vector< vector<long long> > between;

        void build(int layer, int lBound, int rBound) {
            if (layer >= (int)layers.size()) {
                return;
            }
            int bSzLog = (layers[layer]+1) >> 1;
            int bCntLog = layers[layer] >> 1;
            int bSz = 1 << bSzLog;
            int bCnt = 0;
            for (int l = lBound; l < rBound; l += bSz) {
                bCnt++;
                int r = min(l + bSz, rBound);
                pref[layer][l] = v[l];
                for (int i = l+1; i < r; i++) {
                    pref[layer][i] = op(pref[layer][i-1], v[i]);
                }
                suf[layer][r-1] = v[r-1];
                for (int i = r-2; i >= l; i--) {
                    suf[layer][i] = op(v[i], suf[layer][i+1]);
                }
                build(layer+1, l, r);
            }
            for (int i = 0; i < bCnt; i++) {
                long long ans = 0;
                for (int j = i; j < bCnt; j++) {
                    long long add = suf[layer][lBound + (j << bSzLog)];
                    ans = (i == j) ? add : op(ans, add);
                    between[layer][lBound + (i << bCntLog) + j] = ans;
                }
            }
        }
    public:
        inline long long query(int l, int r) {
            if (l == r) {
                return v[l];
            }
            if (l + 1 == r) {
                return op(v[l], v[r]);
            }
            int layer = onLayer[clz[l ^ r]];
            int bSzLog = (layers[layer]+1) >> 1;
            int bCntLog = layers[layer] >> 1;
            int lBound = (l >> layers[layer]) << layers[layer];
            int lBlock = ((l - lBound) >> bSzLog) + 1;
            int rBlock = ((r - lBound) >> bSzLog) - 1;
            long long ans = suf[layer][l];
            if (lBlock <= rBlock) {
                ans = op(ans, between[layer][lBound + (lBlock << bCntLog) + rBlock]);
            }
            ans = op(ans, pref[layer][r]);
            return ans;
        }

        SqrtTree(const vector<long long>& v)
            : n((int)v.size()), lg(log2Up(n)), v(v), clz(1 << lg), onLayer(lg+1) {
            clz[0] = 0;
            for (int i = 1; i < (int)clz.size(); i++) {
                clz[i] = clz[i >> 1] + 1;
            }
            int tlg = lg;
            while (tlg > 1) {
                onLayer[tlg] = (int)layers.size();
                layers.push_back(tlg);
                tlg = (tlg+1) >> 1;
            }
            for (int i = lg-1; i >= 0; i--) {
                onLayer[i] = max(onLayer[i], onLayer[i+1]);
            }
            pref.assign(layers.size(), vector<long long>(n));
            suf.assign(layers.size(), vector<long long>(n));
            between.assign(layers.size(), vector<long long>((int)(1 << lg)));
            build(0, 0, n);
        }
};




unsigned s;
unsigned getNext(){
    s ^= (s << 13);
    s ^= (s >> 17);
    s ^= (s << 5);
    return s;
}




int n;




int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // LOCAL

    unsigned m, seed ;
    cin >> n >> m >> mod >> seed;
    s = seed;
    vector<ll> a(n);
    for(int i = 0; i < n; i++){
        a[i] = getNext();
    }

    SqrtTree st = SqrtTree(a);


    long long ans = 0;
    unsigned left = 0;
    unsigned right = 0;
    for(unsigned i = 0; i < m; i++){
        left = getNext() % n;
        right = getNext() % n;
        if(left > right) swap(left, right);

        long long result = st.query(left, right) % mod;
        ans = (ans + result) % mod;
    }

    cout << ans;

    return 0;
}