Cờ vua

Mùa World Cup vừa rồi là một mùa World Cup thú vị, kịch tính và đầy bất ngờ; có thể nói World Cup 2022 là kì World Cup hay nhất lịch sử, đặc biệt là với cộng đồng ̶̶R̶̶i̶̶c̶̶o̶̶n Sicon. Có lẽ với bin9638 thì đó là một kì World Cup không mấy vui vẻ. Sau khi đã cược hết tiền tiết kiệm vào Đức, ô tô vào Bỉ, laptop và điện thoại vào Tây Ban Nha, đặc biệt là sổ đỏ vào T1, bin9638 đã mất tất cả. Ngỡ rằng sẽ đi nhảy cầu giống như bao con người khác, nhưng bin9638 lại là người không dễ dàng từ bỏ. Vì vậy bin9638 đã tham gia giải cờ vua thế giới để kiếm tiền thưởng bù lại khoản lỗ.

bin9638 đánh với một bàn cờ đặc biệt gồm \(n\) hàng và \(m\) cột, ban đầu ở hàng thứ nhất anh ấy đặt một con mã ở vị trí bất kì. Mỗi nước đi con mã chỉ có thể tiến lên phía trước và đi theo hình chữ L giống như cờ vua. Giả sử con mã đang ở ô \((1;3)\) thì chỉ được đi tới ô \((2;1), (2;5), (3;2)\) hoặc \((3;4)\), ngoài ra con mã cũng không được đi ra ngoài bàn cờ. Tuy nhiên vì bàn cờ của bin9638 dùng là một bàn cờ siêu cổ, từ thời Napoleon đánh cầu lông ăn tiền nên bàn cờ có \(k\) ô đã bị hỏng, tức là không thể đặt quân cờ trên đó.

Bây giờ bin9638 muốn tính xem có bao nhiêu cách đi để đưa con mã tới hàng cuối cùng ( hàng \(n\) ), nhưng vì mải đi chơi với các bạn nữ ̶t̶̶r̶̶o̶̶n̶̶g̶ ̶m̶̶ơ nên anh ấy đành nhờ các bạn giải giúp vậy !

Input

Một dòng gồm \(3\) số nguyên dương \(n,m\) và \(k\).

\(k\) dòng tiếp theo mỗi dòng là \(2\) số nguyên dương \(x, y (x ≤ n, y ≤ m)\) biểu thị ô \((x;y)\) đã bị hỏng.

Output

Gồm một số duy nhất là kết quả khi chia lấy dư cho \(10^9 + 7\).

Example

2 3 2
1 1
2 2

1

4 4 2
3 4
4 4

10

Scoring

Subtask \(1\) (\(20\%\) số điểm): \(n ≤ 10^5, m ≤ 50, k ≤ 50\).

Subtask \(2\) (\(20\%\) số điểm): \(n ≤ 10^{18}, m ≤ 50, k = 0\).

Subtask \(3\) (\(30\%\) số điểm): \(n ≤ 10^{18}, m ≤ 10, k ≤ 50\).

Subtask \(4\) (\(30\%\) số điểm): \(n ≤ 10^{18}, m ≤ 50, k ≤ 50\).