"I do not believe that sad things and difficult things are in vain. If that is fate, then there must be a meaning to it. I will accept them all and become stronger. So—please stop for me." —— Mawaru Penguindrum

If fate is written from the very beginning, what is the meaning of survival?

I want to live for you, and I want you to live for me.

As long as there is one person who needs you, living has meaning.

Lihua and Rosemary shared the fruit of fate together, sharing both love and punishment.

Fate is a predetermined $p \times s$ binary matrix $C$, which is fixed.

Love is a $p \times q$ binary matrix $A$, and punishment is a $q \times s$ binary matrix $B$.

The fruit of fate consists of love and punishment, satisfying $C[i][j]=(\sum\limits_{k=1}^qA[i][k] \times B[k][j]) \pmod 2$.

Even though fate is predetermined, there are many possibilities for love and punishment, and Lihua and Rosemary cannot help but want to calculate them.

They will not simply board the train of fate and arrive at the destination fate has set; they will also transfer to their own fate.

Therefore, there are $m$ fate transfers. At each fate transfer point, Lihua and Rosemary recite a spell in the name of love and transfer their fate.

A fate transfer modifies a certain row of matrix $C$. After each modification, Lihua and Rosemary wish to recalculate the number of possibilities for love and punishment.

Since the number of possibilities can be very large, they only wish to know the answer modulo $1\,000\,000\,007$.

Input

The first line contains five integers: $p, q, s, m, k$.

Next, read the matrix $C$, which consists of $p$ lines, each containing $s$ numbers.

Then, $m$ lines follow, each representing a modification. Each line starts with a number $j$, indicating that the row being modified is the $j \operatorname{xor} (k \cdot \text{ans})$-th row, where $\text{ans}$ is the answer before the modification. Then, $s$ numbers follow, representing the new values for that row.

Output

Output one integer per line representing the answer before any modifications and after each modification.

Examples

Input 1

2 2 2 1 0
0 1
1 0
1 1 0

Output 1

6
18

Constraints

For all data, $1\le p,q,s,m\le 1000$, $k\in\{0,1\}$.

Let $n$ be the maximum of $p, q, s$.

Property $A$ means the data is random; the initial matrix, which row is modified, and the new values are all generated randomly. If there are no extra restrictions, $p, q, s$ are randomly generated in $(n-5, n]$ (e.g., subtask 10). If $p=q=s=o$ is restricted, then $o$ is randomly generated in $(n-100, n]$ (e.g., subtask 6).

Property $B$ means $p=q=s$.

Property $C$ means the initially read matrix $C$ is an identity matrix.