Cho hai bảng hai chiều có kích thước lần lượt là ~M \times N~ và ~R \times L~. Bạn cần giải quyết hai bài toán:

• Bài toán ~1~: Điền giá trị ~0~ hoặc ~1~ vào ~M \times N - T~ ô còn trống trên hình chữ nhật kích thước ~M \times N~ (~M, N \leq 16~), trong hình chữ nhật đó có ~T~ ô không được phép điền bất cứ giá trị nào.

• Bài toán ~2~: Điền giá trị ~0~ hoặc ~1~ vào ~W \times H~ ô trống trên hình chữ nhật thứ hai.

Các cách điền sẽ phải thoả mãn điều kiện:

• Nếu ~i+j~ lẻ thì giá trị tại ô ~(i,j)~ không nhỏ hơn các ô không bị cấm chung cạnh với nó.

• Nếu ~i+j~ chẵn thì giá trị tại ô ~(i,j)~ không lớn hơn các ô không bị cấm chung cạnh với nó.

Yêu cầu: Đếm số lượng cách xếp khác nhau của bài toán ~1~ và bài toán ~2~. Hai cách xếp được gọi là khác nhau nếu khi chồng khít ~2~ cách lên nhau (không xoay hoặc lật) có ít nhất một ô khác giá trị.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~M, N, T~ (~M, N \leq 16~), trong đó ~M, N~ là kích thước hình chữ nhật trong bài toán ~1~.

• Dòng tiếp theo chứa số nguyên dương ~T~ (~T \leq M \times N~), là số lượng ô không được điền giá trị trong bảng đầu tiên.

• ~T~ dòng tiếp theo, mỗi dòng chứa một cặp số ~(i, j)~ là toạ độ ô không được điền giá trị trong bảng đầu tiên (~1 \le i \le M~, ~1 \le j \le N~).

• Dòng cuối cùng gồm hai số nguyên dương ~W, H~ (~W \leq 8~, ~H \leq 10^9~) là kích thước hình của bài toán ~2~.

Output

Gồm hai dòng, dòng thứ ~i~ là số cách xếp cho bài toán ~i~ chia lấy dư cho ~10^9+7~.

Scoring

Sample Input 1

5 5
1
3 3
3 10000

Sample Output 1

42240
463482359

Sample Input 2

2 2
1
2 2
2 2

Sample Output 2

5
7

Notes

Xét test ví dụ thứ hai:

• Các cách điền thoả mãn bài toán ~1~:

  

• Các cách điền thoả mãn bài toán ~2~: