http://poj.openjudge.cn/practice/C26J/

#include <bits/stdc++.h>
using namespace std;

static const int MOD = 167772161;

inline void addmod(int &x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> b(n + 1);
    vector<int> missPos;
    vector<int> seen(n, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        if (b[i] == -1) {
            missPos.push_back(i);
        } else {
            seen[b[i]] = 1;
        }
    }

    vector<int> missVal;
    for (int v = 0; v < n; ++v) {
        if (!seen[v]) missVal.push_back(v);
    }

    const int INF = 1e9;

    vector<int> pref(n + 1, INF), suff(n + 2, INF);

    for (int i = 1; i <= n; ++i) {
        pref[i] = pref[i - 1];
        if (b[i] >= 0) pref[i] = min(pref[i], b[i]);
    }

    for (int i = n; i >= 1; --i) {
        suff[i] = suff[i + 1];
        if (b[i] >= 0) suff[i] = min(suff[i], b[i]);
    }

    vector<vector<int>> maxp(k + 2, vector<int>(k + 2, 0));

    for (int qi = 0; qi < m; ++qi) {
        int l, r;
        cin >> l >> r;

        int alpha = int(lower_bound(missPos.begin(), missPos.end(), l) - missPos.begin());
        int beta = int(upper_bound(missPos.begin(), missPos.end(), r) - missPos.begin());

        int len = beta - alpha;

        int c = min(pref[l - 1], suff[r + 1]);
        if (c >= INF) c = n;

        int p = int(lower_bound(missVal.begin(), missVal.end(), c) - missVal.begin());

        if (p == 0 || len == 0 || len == k) continue;

        int L = alpha + 1;
        int R = beta;

        maxp[L][R] = max(maxp[L][R], p);
    }

    vector<vector<int>> mx(k + 2, vector<int>(k + 3));
    vector<vector<int>> mn(k + 2, vector<int>(k + 3));

    vector<vector<int>> clL(k + 2, vector<int>(k + 2));
    vector<vector<int>> clR(k + 2, vector<int>(k + 2));

    auto build_closure = [&](int t) {
        for (int i = 0; i <= k + 1; ++i) {
            fill(mx[i].begin(), mx[i].end(), 0);
            fill(mn[i].begin(), mn[i].end(), k + 1);
        }

        for (int l = 1; l <= k; ++l) {
            for (int r = l; r <= k; ++r) {
                if (maxp[l][r] >= t) {
                    mx[l][r] = l;
                    mn[l][r] = r;
                }
            }
        }

        for (int L = 1; L <= k; ++L) {
            for (int R = k; R >= 1; --R) {
                mx[L][R] = max(mx[L][R], mx[L - 1][R]);
                mx[L][R] = max(mx[L][R], mx[L][R + 1]);

                mn[L][R] = min(mn[L][R], mn[L - 1][R]);
                mn[L][R] = min(mn[L][R], mn[L][R + 1]);
            }
        }

        for (int L = 1; L <= k; ++L) {
            for (int R = L; R <= k; ++R) {
                if (mx[L][R] == 0) {
                    clL[L][R] = 1;
                    clR[L][R] = k;
                } else {
                    clL[L][R] = mx[L][R];
                    clR[L][R] = mn[L][R];
                }
            }
        }
    };

    vector<vector<int>> dp(k + 2, vector<int>(k + 2, 0));
    vector<vector<int>> temp(k + 2, vector<int>(k + 2, 0));
    vector<vector<int>> ndp(k + 2, vector<int>(k + 2, 0));

    vector<vector<int>> rowPref(k + 2, vector<int>(k + 2, 0));
    vector<vector<int>> colSuf(k + 2, vector<int>(k + 2, 0));
    vector<vector<int>> start(k + 2, vector<int>(k + 2, 0));

    build_closure(1);

    for (int q = 1; q <= k; ++q) {
        dp[clL[q][q]][clR[q][q]] = 1;
    }

    for (int t = 2; t <= k; ++t) {
        build_closure(t);

        for (int i = 0; i <= k + 1; ++i) {
            fill(temp[i].begin(), temp[i].end(), 0);
            fill(ndp[i].begin(), ndp[i].end(), 0);
            fill(rowPref[i].begin(), rowPref[i].end(), 0);
            fill(colSuf[i].begin(), colSuf[i].end(), 0);
            fill(start[i].begin(), start[i].end(), 0);
        }

        for (int L = 1; L <= k; ++L) {
            for (int R = L; R <= k; ++R) {
                int val = dp[L][R];
                if (!val) continue;

                int a = clL[L][R];
                int b2 = clR[L][R];

                addmod(temp[a][b2], val);
            }
        }

        for (int a = 1; a <= k; ++a) {
            int s = 0;
            for (int b2 = a; b2 <= k; ++b2) {
                addmod(s, temp[a][b2]);
                rowPref[a][b2] = s;
            }
        }

        for (int b2 = 1; b2 <= k; ++b2) {
            int s = 0;
            for (int a = b2; a >= 1; --a) {
                addmod(s, temp[a][b2]);
                colSuf[b2][a] = s;
            }
        }

        for (int x = 1; x <= k; ++x) {
            int b2 = x;

            while (b2 <= k) {
                int L = clL[x][b2];
                int R = clR[x][b2];
                int s = b2;

                while (b2 + 1 <= k &&
                       clL[x][b2 + 1] == L &&
                       clR[x][b2 + 1] == R) {
                    ++b2;
                }

                if (L == x) {
                    start[x][R] = s;
                }

                ++b2;
            }
        }

        for (int L = 1; L <= k; ++L) {
            for (int R = L; R <= k; ++R) {
                int val = temp[L][R];
                if (val && R - L + 1 >= t) {
                    addmod(ndp[L][R], val);
                }
            }
        }

        for (int b2 = 1; b2 <= k; ++b2) {
            for (int q = 1; q < b2; ++q) {
                int L = clL[q][b2];
                int R = clR[q][b2];

                if (L == q) {
                    int add = colSuf[b2][q + 1];
                    if (add) addmod(ndp[L][R], add);
                }
            }
        }

        for (int a = 1; a <= k; ++a) {
            for (int q = a + 1; q <= k; ++q) {
                int L = clL[a][q];
                int R = clR[a][q];

                if (R != q) continue;

                int add = 0;

                if (L < a) {
                    int s = start[L][R];

                    if (s > a) {
                        add = rowPref[a][s - 1];
                    }
                } else {
                    add = rowPref[a][q - 1];
                }

                if (add) addmod(ndp[L][R], add);
            }
        }

        dp.swap(ndp);
    }

    int ans = 0;

    for (int L = 1; L <= k; ++L) {
        for (int R = L; R <= k; ++R) {
            addmod(ans, dp[L][R]);
        }
    }

    cout << ans << '\n';
    return 0;
}