+ محدودیت ز مان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما درگیری‌هایش باعث شدند او پس از شروع مسابقه برسد. محمدرضاص پس از اینکه متوجه شد دیگر نمیتواند در مسابقه‌ی ششم کوئرا شرکت کند، از ناراحتی از هوش رفت. او در خواب و خیال خودرا در یک صفحه شطرنجی با $H$ سطر و $W$ ستون یافت. او دید که سطرهای این جدول با اعداد طبیعی ۱ تا $H$ از بالا به پایین و ستون‌های آن با اعداد طبیعی ۱ تا $W$ از چپ به راست شماره گذاری شده‌اند و خودش روی خانه‌ی در سطر و ستون اول(خانه‌ی بالا-چپ جدول)، سوار بر یک اسب سفید متنظر حرکت است. همچنین دید که $n$ خانه از صفحه شطرنج شامل مانع هستند (یعنی اسب او نمیتاند وارد آن خانه‌ها شود) و روی خانه‌ی در سطر $H$ و ستون $W$ (خانه‌ی پایین-چپ جدول) دارد مسابقه‌ی کوئرا برگزار میشود! اسبی که محمدرضاص روی آن سوار است مانند همه‌ی اسب‌های شطرنج، میتواند بصورت $L$ حرکت کند. یعنی به خانه‌هایی میتواند برود که فاصله اقلیدسی آنها با خانه‌ی کنونی برابر $\sqrt 5$ است. محمدرضاص با خوشحالی قصد حرکت کردن به سمت خانه‌ی مسابقه کرد، اما متوجه شد که اسب رویاهای او شل است و تنها میتواند به سمت پایین-راست حرکت کند؛ یعنی پس از هر حرکت باید شماره سطر و ستونش زیاد بشود. دقت کنید که ممکن است محمدرضاص با این وضعیت نتواند به خانه‌ی مسابقه برسد، مثلاً اگر $H = 3$ و $W = 10$ اینگونه میشود. حال محمدرضاص میخواهد از فضای خیالی خود سوء استفاده کرده و از خود بیشترین تعداد کپی ممکن را بگیرد و از مسیرهای مختلف به محل برگزاری مسابقه برود. (بدون علم به اینکه مسابقه حضوری نیست!) اکنون محمدرضاص بیدار و هشیار شده و اطلاعات صفحه شطرنج خیالش را به ما داده است. با ورودی گرفتن $W, H$ و خانه‌های شامل مانع، تعداد مسیر‌های مختلفی که محمدرضاص میتوانست با اسب خود از گوشه‌ی بالا-چپ به گوشه‌ی پایین-راست جدول برود را خروجی دهید. چون که این عدد میتواند بسیار بزرگ باشد، باقیمانده‌ی این عدد پس از تقسیم بر $10007$ را خروجی دهید. # ورودی سطر اول ورودی شامل سه عدد $H$ و $W$ و $n$ است که به ترتیب نمایانگر تعداد سطرها و تعداد ستون‌های صفحه شطرنج خیالی محمدرضاص و تعداد خانه‌های شامل مانع آن هستند. سپس در $i$ مین سطر از هریک از $n$ سطر بعدی، دو عدد $h_i$ و $w_i$ آمده‌اند که نمایانگر سطر و ستون $i$مین مانع هستند. $$0 \le n \le 10$$$$1 \le h_i \le H \le 100\ 000\ 000$$$$1 \le w_i \le W \le 100\ 000\ 000$$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که برابر باقیمانده‌ی تعداد مسیرهای محمدرضاص پس از تقسیم بر $10007$ است. # مثال ## ورودی نمونه ۱ ``` 1 1 0 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 7 10 2 1 2 7 1 ``` ## خروجی نمونه ۲ ``` 5 ```

حل سؤال در بانک سؤالات