جدولی $n \times 4$ دار یم که بعضی از خانه‌
های آن مسدود است. می
دانیم که دو ستون ۱ و $n$، خانه مسدود ندارند. به دنبال تعداد مسیر
های موجود در جدول از خانه بالا سمت چپ به خانه بالا سمت راست هستیم. هر مسیر دنباله
ای $n$-تایی از خانه‌
های نامسدود جدول است که از خانه بالا سمت چپ آغاز شده و به خانه بالا سمت راست منتهی می
شود و هر دو خانه متوالی آن با یکدیگر اشتراک رأسی یا یالی دارند. از آن
جایی که ممکن است این تعداد زیاد باشد، باقی
مانده‌
ی جواب در تقسیم بر $10^9 + 7$ را در خروجی نشان دهید. ## ورودی در ابتدا $n$ ($1 \leq n \leq 10^{18}$ ) تعداد ستون
های جدول و سپس $m$ ($1 \leq m \leq 100$ ) تعداد خانه های مسدود می
آید. سپس در $m$ سطر بعد در هر سطر مختصات خانه های مسدود می
آید به این صورت که ابتدا شماره سطر و سپس شماره ستون خانه مسدود می
آیند. ## خروجی در تنها سطر خروجی، پاسخ مسأله را چاپ کنید (پاسخ مسئله باقی
مانده‌
ی جواب در تقسیم بر $10^9 + 7$ است). ## مثال ورودی نمونه ۱ ``` 5 2 1 2 2 3 ``` خروجی نمونه ۱ ``` 3 ``` ورودی نمونه ۲ ``` 28 2 3 10 2 10 ``` خروجی نمونه ۲ ``` 368245731 ```