Chỉ còn \(n\) ngày nữa là Tú Anh phải làm bài thi cuối kì. Tú Anh khá lo lắng về ba môn học. Thứ nhất là Phương pháp tối ưu, thứ hai Thuật toán ứng dụng và thứ ba là Tiếng anh chuyên ngành. Bạn ấy sử dụng một phần mềm giúp sắp xếp lịch ôn các môn theo từng ngày. Tuy nhiên phần mềm bị trục trặc và lịch ôn của một số ngày bị mất, chỉ còn lại \(k\) ngày. Trong \(k\) ngày đó, mỗi ngày sẽ ôn một trong ba môn trên.

Ngoài \(k\) ngày đó ra, Tú Anh phải tự chọn môn để học. Nhưng dạo này Tú Anh rất hay bị stress, nếu phải ôn một môn liên tiếp trong 3 ngày thì bạn ấy sẽ không thể chịu được. Hãy tính xem có bao nhiêu cách chọn môn học cho từng ngày sao cho bạn ấy không bị stress.

Input

Dòng đầu là \(2\) số nguyên \(n, k\) \((3 \le n \le 100, 1 \le k \le n)\).

\(k\) dòng tiếp theo, mỗi dòng chứa 2 số \(a_i\), \(b_i\) thể hiện ngày thứ \(a_i\) Tú Anh sẽ ôn môn thứ \(b_i\) \((1 \le a_i \le n, 1 \le b_i \le 3)\).

Output

In ra số nguyên dương thể hiện các chọn môn học. Vì kết quả có thể rất lớn nên chỉ in ra phần dư khi lấy kết quả chia cho \(1000000007\).

Example

Sample Input

5 4
1 1
3 1
4 2
5 3

Sample Output

2

Giải thích: Tú Anh chỉ có 2 cách chọn cho ngày thứ \(2\) là môn thứ hai và môn thứ ba. Vì nếu chọn môn thứ nhất thì sẽ có ba ngày học môn thứ nhất => bạn ấy sẽ bị stress :((