SolarPea thinks inversion is beautiful.

For a 01-sequence $Z$ with length $n$ and a constant $c$, SolarPea defines the rating of $Z$ is:

$T(Z,c)=c^{\sum_{i=1}^{n-1}\sum_{j=i+1}^n[Z_i>Z_j]}$

PolarSea has two integer sequences $X$ and $Y$ with length $k (\forall_{1\leq i\leq k}, 1\leq X_i \leq n, 0\leq Y_i\leq 1)$. PolarSea likes a 01-sequence $Z$ with length $n$ if and only if $\forall_{1\leq i\leq k}, Z_{X_i}=Y_i$.

SolarPea wrote all 01-sequences which have length $n$ and contain $m$ '1's on the paper. PolarSea saw it and crossed out all sequences that he doesn't like. Now you're given $c$, please calculate the sum of the rating s of the remaining sequences on the paper.

Since the answer could be very large, you should output it modulo $1065977431$ (a prime number).

It is guaranteed that $c$ is generated randomly.

The first line contains four non-negative integers $n,m,k,c$$(1\leq n\leq 10^{18},0\leq m \leq \min(n,10^7),0\leq k\leq \min(n,30),2\leq c< 1065977431)$.

The next $k$ lines, each line contains two non-negative intergers $X_i$ and $Y_i (1\leq X_i \leq n, 0\leq Y_i\leq 1)$.

It is guaranteed that all $X_i$ are pairwise different.

Output the answer modulo $1065977431$.

There are two remaining sequences ${1, 1, 0}$ and ${0, 1, 1}$.

$T({1, 1, 0},c)=c^2=100$, $T({0, 1, 1} ,c)=c^0=1$, so the answer is $100+1=101$.