Little L ha un pezzo di cioccolato di dimensioni $L \times W \times H$. All'interno del cioccolato ci sono $n$ mandorle, con la $i$-esima mandorla situata al centro del cubo unitario $[x_i - 1, x_i] \times [y_i - 1, y_i] \times [z_i - 1, z_i]$. Nessuna coppia di mandorle occupa la stessa posizione.

Ora, Little L vuole tagliare questo pezzo di cioccolato in diversi pezzi più piccoli. Nello specifico, vuole effettuare rispettivamente $p, q, r$ tagli lungo le tre dimensioni. Ogni taglio deve essere effettuato lungo coordinate intere, non possono essere effettuati due tagli alla stessa coordinata nella stessa dimensione, e i tagli non possono essere effettuati sui bordi del cioccolato (cioè alle coordinate $0$ oppure $L, W, H$).

Formalmente, un taglio nella direzione $x$ alla coordinata $k$ ($0 < k < L$) significa tagliare il cioccolato lungo il piano $x = k$. Lo stesso vale per le direzioni $y$ e $z$.

Inoltre, per i $(p + 1)(q + 1)(r + 1)$ pezzi di cioccolato ottenuti dopo i tagli, Little L spera che ogni pezzo contenga lo stesso numero di mandorle. Little L vuole sapere quanti metodi di taglio essenzialmente diversi soddisfano questa condizione. Due metodi di taglio sono considerati diversi se esiste una posizione in una dimensione tale che il primo metodo taglia in questa posizione mentre il secondo no. Stampa il risultato modulo $10^9 + 7$.

Input

La prima riga di ogni caso di test contiene tre interi $L, W, H$ ($1 \le L, W, H \le 10^9$), che rappresentano le dimensioni del cioccolato.

La seconda riga contiene tre interi $p, q, r$ ($0 \le p, q, r \le 10^6$), che rappresentano rispettivamente il numero di tagli nelle direzioni $x$, $y$ e $z$.

La terza riga contiene un intero $n$ ($1 \le n \le 10^6$), che rappresenta il numero di mandorle.

Le successive $n$ righe contengono ciascuna tre interi $x_i, y_i, z_i$ ($1 \le x_i \le L, 1 \le y_i \le W, 1 \le z_i \le H$), che rappresentano la posizione di una mandorla. È garantito che tutte le terne $(x_i, y_i, z_i)$ siano distinte.

Output

Una singola riga contenente un intero che rappresenta il risultato modulo $10^9 + 7$.

Esempi

Input 1

4 4 1
1 1 0
4
1 2 1
2 4 1
3 1 1
4 3 1

Output 1

1

Input 2

3 3 3
1 1 1
3
1 1 1
2 2 2
3 3 3

Output 2

0

Input 3

9 9 9
1 1 1
8
1 1 2
2 2 8
1 9 1
2 8 9
8 2 1
9 2 9
9 8 1
8 9 7

Output 3

180