Lát gạch hành lang

Năm ngoái, khuôn viên trường Đại học FPT được dùng làm khu cách ly cho bệnh nhân COVID-19. Hiện nay, số ca mắc mới mỗi ngày đã giảm đáng kể và khuôn viên đã trở lại là môi trường đại học bình thường. Nhà trường quyết định lát lại gạch hành lang.

Hành lang của trường Đại học FPT có dạng hình chữ nhật kích thước $r\times n$, và sẽ được lát lại bằng các viên gạch men kích thước $1\times 2$ (có thể đặt ngang hoặc dọc). Trên hành lang có $k$ vị trí là cột trụ, các vị trí này không được lát gạch. Mọi ô còn lại phải được lát, và các viên gạch không được chồng lên nhau.

Hãy đếm số cách lát lại hành lang.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $r$, $n$ và $k$.
• $k$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ ($1\le x\le r$, $1\le y\le n$) mô tả vị trí của một cột trụ (hàng $x$, cột $y$). Không có hai cột trụ nào ở cùng một vị trí.

Dữ liệu ra

In ra một số nguyên là số cách lát lại hành lang. Vì số này có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le r\le 6$.
• $1\le n\le {10}^{12}$.
• $0\le k\le 10$.

Ví dụ