Viện Công nghệ thông tin đang được tu sửa và nâng cấp. Một trong những hạng mục công việc là lát lại hành lang nối từ phòng làm việc sang phòng đặt máy chủ. Hành lang có độ rộng \(2\) và độ dài \(n\) được biểu thị như một lưới ô vuông gồm \(2\) hàng và \(n\) cột. Để lát người ta dùng các viên gạch men loại kích thước \(1 \times 1\) và kích thước \(1 \times 2\) với số lượng dự trữ không hạn chế. Các viên gạch \(1 \times 2\) có thể lát dọc hoặc xoay ngang. Trước đây hành lang được lát bằng các viên gạch kích thước \(1 \times 1\) và có \(k\) viên gạch bên dưới lắp các thiết bị điện tử, trong đó viên thứ \(i\) ở hàng \(r_{i}\) và cột \(c_{i}\). Ban Giám đốc viện không muốn lắp lại hệ thống điện tử vốn đang hoạt động rất tốt, nên yêu cầu đánh dấu những viên này và không được bóc chúng lên trong quá trình lát nền.

Bộ phận thi công phàn nàn về yêu cầu trên, vì như thế sẽ hạn chế khả năng lát. Điều này làm Trưởng phòng vật tư đề nghị bộ phận lập trình tính số phương án lát nền khác nhau mà vẫn đảm bảo yêu cầu đã nêu, để bên thi công thấy có nhiều cách làm khác nhau.

Bạn hãy tính và đưa ra số phương án lát nền theo mô-đun \(10^{9} + 7\) (tức là đưa ra số dư của số phương án lát nền chia cho \(10^{9} + 7\)). Hai phương án gọi là khác nhau nếu tồn tại hai ô kề cạnh trong phương án này được phủ bằng một viên gạch \(1 \times 2\), còn phương án kia thì không được phủ bằng một viên gạch \(1 \times 2\).

Ví dụ với \(n = 2\) và \(k = 0\) (không có viên gạch kích thước \(1 \times 1\) nào được đánh dấu), ta có \(7\) phương án lát nền như minh họa trong hình dưới đây:

Ví dụ khác với \(n = 3\) và \(k = 1\) viên gạch kích thước \(1 \times 1\) được đánh dấu ở vị trí \((1,\ 2)\) (ô được tô kín trong hình vẽ), ta có \(8\) phương án lát nền như minh họa trong hình dưới đây:

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên \(n\) và \(k\) \(\left( 1 \leq n \leq 10^{5};0 \leq k < 2n \right)\).

+ Dòng thứ \(i\) trong \(k\) dòng tiếp theo chứa hai số nguyên \(r_{i}\) và \(c_{i}\) \(\left( 1 \leq r_{i} \leq 2;1 \leq c_{i} \leq n \right)\).

Kết quả:

+ Ghi một số nguyên là số phương án lát nền theo mô-đun \(10^{9} + 7\).

Ví dụ:

Ràng buộc:

+ Có 20% số test ứng với 20% số điểm của bài thỏa mãn: \(1 \leq n \leq 8;k = 0\);

+ 20% số test khác ứng với 20% số điểm của bài thỏa mãn: \(1 \leq n \leq 10^{3};k = 0\);

+ 20% số test khác ứng với 20% số điểm của bài thỏa mãn: \(1 \leq n \leq 10^{5};k = 0\);

+ 20% số test khác ứng với 20% số điểm của bài thỏa mãn: \(1 \leq n \leq 10^{5};k = 1\);

+ 20% số test còn lại ứng với 20% số điểm của bài không có thêm ràng buộc nào.