Hành lang nối từ phòng làm việc sang phòng đặt server có dạng hình chữ nhật kích thước ~2 \times n~ (dài ~n~, rộng ~2~). Viện CNTT muốn lát lại nền bằng gạch men loại ~1\times 1~ và ~1\times 2~ (số lượng không hạn chế). Gạch ~1\times 2~ có thể đặt:

• Dọc: phủ hai ô ~(x,1)~ và ~(x,2)~ trong cùng một cột.
• Ngang: phủ hai ô ~(x,y)~ và ~(x+1,y)~ trên cùng một hàng.

Trước đây hành lang đã được lát bằng gạch ~1\times 1~, và dưới một số viên có lắp thiết bị điện tử đang hoạt động. Ban Giám đốc yêu cầu không được bóc các viên này lên. Có tất cả ~k~ viên như vậy, viên thứ ~i~ nằm tại ô ~(x_i, y_i)~, với ~1 \le x_i \le n~, ~1 \le y_i \le 2~.

Hãy đếm số phương án lát lại toàn bộ hành lang sao cho các ô đã đánh dấu bắt buộc vẫn là gạch ~1\times 1~ (tức là không được có viên ~1\times 2~ nào phủ lên các ô này).

Yêu cầu

Tính số cách lát kín hình chữ nhật ~2 \times n~ bằng các viên gạch ~1\times 1~ và ~1\times 2~, với điều kiện mọi ô trong tập đánh dấu ~(x_i, y_i)~ bắt buộc được phủ bởi gạch ~1\times 1~.

Hai phương án được coi là khác nhau nếu tồn tại ít nhất một ô mà trong một phương án ô đó được phủ bởi gạch ~1\times 1~, còn trong phương án kia ô đó được phủ bởi gạch ~1\times 2~.

In kết quả theo mô đun ~10^9+7~.

Dữ liệu

• Dòng đầu chứa hai số nguyên ~n~ và ~k~.
• ~k~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~ và ~y_i~, mô tả một ô bắt buộc giữ nguyên gạch ~1\times 1~.

Kết quả

In ra một số nguyên: số phương án lát thỏa mãn, lấy theo mô đun ~10^9+7~.

Ví dụ

Ví dụ 1

Input

3 1
2 1

Output

8

Giải thích

Ví dụ 1

Hành lang có kích thước ~2\times 3~, trong đó ô ~(2,1)~ bắt buộc là gạch ~1\times 1~ nên không viên ~1\times 2~ nào được phép phủ qua ô này. Khi xét tất cả các cách lát kín phần còn lại bằng gạch ~1\times 1~ và ~1\times 2~, ta có tổng cộng ~8~ phương án (lấy theo mô đun ~10^9+7~ vẫn là ~8~).

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^5~
• ~0 \le k < 2n~
• ~1 \le x_i \le n~, ~1 \le y_i \le 2~