----- برای آگاهی از مسابقات Quera به کانال تلگرام مسابقات بپیوندید. @quera_contests https://telegram.me/quera_contests

خیال شطرنجی


  • محدودیت ز مان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

محمدرضاص که کنکورش را داده، میخواهد در همه‌ی مسابقات برنامه‌نویسی کوئرا شرکت کند؛ اما درگیری‌هایش باعث شدند او پس از شروع مسابقه برسد.

محمدرضاص پس از اینکه متوجه شد دیگر نمیتواند در مسابقه‌ی ششم کوئرا شرکت کند، از ناراحتی از هوش رفت. او در خواب و خیال خودرا در یک صفحه شطرنجی با HH سطر و WW ستون یافت. او دید که سطرهای این جدول با اعداد طبیعی ۱ تا HH از بالا به پایین و ستون‌های آن با اعداد طبیعی ۱ تا WW از چپ به راست شماره گذاری شده‌اند و خودش روی خانه‌ی در سطر و ستون اول(خانه‌ی بالا-چپ جدول)، سوار بر یک اسب سفید متنظر حرکت است. همچنین دید که nn خانه از صفحه شطرنج شامل مانع هستند (یعنی اسب او نمیتاند وارد آن خانه‌ها شود) و روی خانه‌ی در سطر HH و ستون WW (خانه‌ی پایین-چپ جدول) دارد مسابقه‌ی کوئرا برگزار میشود!

اسبی که محمدرضاص روی آن سوار است مانند همه‌ی اسب‌های شطرنج، میتواند بصورت LL حرکت کند. یعنی به خانه‌هایی میتواند برود که فاصله اقلیدسی آنها با خانه‌ی کنونی برابر 5\sqrt 5 است. محمدرضاص با خوشحالی قصد حرکت کردن به سمت خانه‌ی مسابقه کرد، اما متوجه شد که اسب رویاهای او شل است و تنها میتواند به سمت پایین-راست حرکت کند؛ یعنی پس از هر حرکت باید شماره سطر و ستونش زیاد بشود.

دقت کنید که ممکن است محمدرضاص با این وضعیت نتواند به خانه‌ی مسابقه برسد، مثلاً اگر H=3H = 3 و W=10W = 10 اینگونه میشود.

حال محمدرضاص میخواهد از فضای خیالی خود سوء استفاده کرده و از خود بیشترین تعداد کپی ممکن را بگیرد و از مسیرهای مختلف به محل برگزاری مسابقه برود. (بدون علم به اینکه مسابقه حضوری نیست!)

اکنون محمدرضاص بیدار و هشیار شده و اطلاعات صفحه شطرنج خیالش را به ما داده است. با ورودی گرفتن W,HW, H و خانه‌های شامل مانع، تعداد مسیر‌های مختلفی که محمدرضاص میتوانست با اسب خود از گوشه‌ی بالا-چپ به گوشه‌ی پایین-راست جدول برود را خروجی دهید.

چون که این عدد میتواند بسیار بزرگ باشد، باقیمانده‌ی این عدد پس از تقسیم بر 1000710007 را خروجی دهید.

ورودی🔗

سطر اول ورودی شامل سه عدد HH و WW و nn است که به ترتیب نمایانگر تعداد سطرها و تعداد ستون‌های صفحه شطرنج خیالی محمدرضاص و تعداد خانه‌های شامل مانع آن هستند.

سپس در ii مین سطر از هریک از nn سطر بعدی، دو عدد hih_i و wiw_i آمده‌اند که نمایانگر سطر و ستون iiمین مانع هستند.

0n100 \le n \le 101hiH100 000 0001 \le h_i \le H \le 100\ 000\ 0001wiW100 000 0001 \le w_i \le W \le 100\ 000\ 000

خروجی🔗

تنها سطر خروجی باید شامل یک عدد باشد که برابر باقیمانده‌ی تعداد مسیرهای محمدرضاص پس از تقسیم بر 1000710007 است.

مثال🔗

ورودی نمونه ۱🔗

1 1 0
Plain text

خروجی نمونه ۱🔗

1
Plain text

ورودی نمونه ۲🔗

7 10 2
1 2
7 1
Plain text

خروجی نمونه ۲🔗

5
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.