بازی با کلمات

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

در این سوال باید برنامه‌ای بنویسید که $n$ کلمه از ورودی دریافت کرده و ترتیب کلمات آن را برعکس کند و در خروجی چاپ کند.

ورودی🔗

در سطر اول ورودی $n$ می‌آید که نمایانگر تعداد کلمات است. در سطر دوم ورودی $n$ کلمه می‌آید که با فاصله از هم جدا شده‌اند. کاراکترهای به کار رفته در این کلمات حروف کوچک و بزرگ انگلیسی می‌باشند. مجموع طول تمام کلمه‌ها از 1000 کاراکتر بیشتر نیست. $1 \le n \le 100$

خروجی🔗

در تنها سطر خروجی کلمات داده شده را به ترتیب برعکس ورودی چاپ کنید. دقت کنید که کوچک و بزرگ بودن حروف خروجی باید مانند حروف ورودی باشد.

مثال🔗

ورودی نمونه🔗

11
I Am from Iran it iS rainy and i like rain

خروجی نمونه🔗

rain like i and rainy iS it Iran from Am I

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دیجیکالا برای ارسال بسته‌های سنگین مانند یخچال و غیره نیاز به **دقیقاً** دو نفر دارد که بتوانند بسته را جابه‌جا کنند. از این رو دو نفر را به عنوان پیک استخدام کرده است. هر کدام از این دو نفر در بازه‌هایی از روز‌های ماه می‌توانند سر کار بروند. حالا مسئولین دیجیکالا می‌خواهند بدانند که در چند روز از ماه آنها می‌توانند بسته‌های سنگین را ارسال کنند. # ورودی در سطر اول ورودی دو عدد $n$ و $m$‌ می‌آید که به ترتیب نمایانگر تعداد بازه‌هایی است که پیک اول و دوم سر کار می‌آیند. سپس در $n$ خط بعدی در هر خط یک بازه‌‌ی کاری پیک اول می‌آید. بعد از آن در هر یک از $m$ خط بعدی یکی از بازه‌های کاری پیک دوم می‌آید. همچنین نحوه ورودی دادن بازه‌ها به این شکل است: در یک خط دو عدد $l$ و $r$ می‌آید که اولی نمایانگر شروع بازه و دومی نمایانگر پایان بازه می‌باشد.$$ 1 \le n,m \le 10 $$ $$ 1 \le l \le r \le 30 $$ دقت کنید که هیچ کدام از دو بازه‌ی یک پیک با هم اشتراک ندارند. همچنین تمام بازه‌ها شامل نقطه‌ی شروع و پایان نیز می‌شوند. همچنین توجه کنید که در ورودی هیچ یک از بازه‌های کاری یک پیک دو بار نخواهد آمد. # خروجی در تنها خط خروجی تعداد روزهایی را که دیجیکالا می‌تواند بسته‌ی سنگین ارسال کند را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 2 1 8 9 15 18 25 15 20 8 10 ``` ## خروجی نمونه ۱ ``` 7 ``` توضیح: روزهایی که دیجیکالا می‌تواند بسته‌ی سنگین ارسال کند: 8 ، 9 ، 10 ، 15 ، 18 ، 19 ، 20

لجستیک دیجیکالا

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

دیجیکالا برای ارسال بسته‌های سنگین مانند یخچال و غیره نیاز به دقیقاً دو نفر دارد که بتوانند بسته را جابه‌جا کنند. از این رو دو نفر را به عنوان پیک استخدام کرده است. هر کدام از این دو نفر در بازه‌هایی از روز‌های ماه می‌توانند سر کار بروند. حالا مسئولین دیجیکالا می‌خواهند بدانند که در چند روز از ماه آنها می‌توانند بسته‌های سنگین را ارسال کنند.

ورودی🔗

در سطر اول ورودی دو عدد $n$ و $m$ ‌ می‌آید که به ترتیب نمایانگر تعداد بازه‌هایی است که پیک اول و دوم سر کار می‌آیند. سپس در $n$ خط بعدی در هر خط یک بازه‌‌ی کاری پیک اول می‌آید. بعد از آن در هر یک از $m$ خط بعدی یکی از بازه‌های کاری پیک دوم می‌آید. همچنین نحوه ورودی دادن بازه‌ها به این شکل است:

در یک خط دو عدد $l$ و $r$ می‌آید که اولی نمایانگر شروع بازه و دومی نمایانگر پایان بازه می‌باشد. $1 \le n,m \le 10$ $1 \le l \le r \le 30$

دقت کنید که هیچ کدام از دو بازه‌ی یک پیک با هم اشتراک ندارند. همچنین تمام بازه‌ها شامل نقطه‌ی شروع و پایان نیز می‌شوند. همچنین توجه کنید که در ورودی هیچ یک از بازه‌های کاری یک پیک دو بار نخواهد آمد.

خروجی🔗

در تنها خط خروجی تعداد روزهایی را که دیجیکالا می‌تواند بسته‌ی سنگین ارسال کند را خروجی دهید.

مثال🔗

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

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

توضیح: روزهایی که دیجیکالا می‌تواند بسته‌ی سنگین ارسال کند:

8 ، 9 ، 10 ، 15 ، 18 ، 19 ، 20

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بد خواه، بدِ مردم را میخواهد. از این رو بر آن شده است که مردم را سرگرم کند و وقتشان را تلف کند تا به کار های مهم زندگی نرسند. او ابتدا مردم را به یک اتاق دعوت می‌کند. سپس کیسه ای را با $m$ توپ سیاه و $n$ توپ سفید پر میکند. سپس از شخصی میخواهد تا دو توپ از کیسه بیرون بیاورد. اگر دو توپ هم رنگ بودند، یک توپ سفید جدید در داخل کیسه بیاندازد و اگر همرنگ نبودند، یک توپ سیاه جدید داخل کیسه بیاندازد. سپس دو توپ خارج شده را دور بیاندازد. آن شخص باید اینقدر این کار را تکرار کند تا دقیقاً یک توپ داخل کیسه باقی بماند. بعد از اینکه بد خواه از کسی خواهش کرد که او این کار را انجام دهد، قبل از این که آن شخص شروع به انجام کار کند بدخواه از آن اتاق بیرون رفته و وقتی که دقیقا یک توپ در کیسه باقی مانده بود به اتاق برمیگردد. دقت کنید که بدخواه از ترتیب بیرون آوردن توپ‌ها بی اطلاع است و تنها $n$ و $m$ را میداند. از آنجایی که بدخواه دنبال سرگرم کردن مردم است، میخواهد رنگ توپ داخل کیسه را پیش‌بینی کند. اما از آنجایی که ذاتاً آدم بی‌هنریست، توانایی انجام این کار را ندارد. از این رو بر آن شده است که از شما کمک بگیرد و از شما می‌خواهد که رنگ توپ را فقط با دانستن $n$ و $m$ برای او پیش بینی کنید یا به او بگویید امکان پیش‌بینی وجود ندارد زیرا امکان دارد توپ باقی‌مانده سفید یا سیاه (بسته به ترتیب بیرون آوردن توپ‌ها) باشد تا او بتواند با انجام حرکات موزون مردم را سرگرم کند تا ناتوانی او در پیش‌بینی را فراموش کنند. # ورودی سطر اول ورودی شامل دو عدد $m$ و $n$ است که به ترتیب نشان دهنده‌ ی تعداد توپ‌های سیاه و تعداد توپ‌های سفید اند. $$ 1 \le m,n \le 1000\ 000\ 000$$ # خروجی تنها سطر خروجی باید شامل یک کلمه باشد: + $white$ : به معنای اینکه توپ آخر سفید است. + $black$ : به معنای اینکه توپ آخر سیاه است. + $no prediction$ : به معنای اینکه امکان پیش‌بینی وجود ندارد. # مثال ## ورودی نمونه ۱ ``` 2 2 ``` ## خروجی نمونه ۱ ``` white ``` ## ورودی نمونه ۲ ``` 3 6 ``` ## خروجی نمونه ۲ ``` black ```

توپ و کیسه

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

بد خواه، بدِ مردم را میخواهد. از این رو بر آن شده است که مردم را سرگرم کند و وقتشان را تلف کند تا به کار های مهم زندگی نرسند. او ابتدا مردم را به یک اتاق دعوت می‌کند. سپس کیسه ای را با $m$ توپ سیاه و $n$ توپ سفید پر میکند. سپس از شخصی میخواهد تا دو توپ از کیسه بیرون بیاورد. اگر دو توپ هم رنگ بودند، یک توپ سفید جدید در داخل کیسه بیاندازد و اگر همرنگ نبودند، یک توپ سیاه جدید داخل کیسه بیاندازد. سپس دو توپ خارج شده را دور بیاندازد. آن شخص باید اینقدر این کار را تکرار کند تا دقیقاً یک توپ داخل کیسه باقی بماند. بعد از اینکه بد خواه از کسی خواهش کرد که او این کار را انجام دهد، قبل از این که آن شخص شروع به انجام کار کند بدخواه از آن اتاق بیرون رفته و وقتی که دقیقا یک توپ در کیسه باقی مانده بود به اتاق برمیگردد. دقت کنید که بدخواه از ترتیب بیرون آوردن توپ‌ها بی اطلاع است و تنها $n$ و $m$ را میداند. از آنجایی که بدخواه دنبال سرگرم کردن مردم است، میخواهد رنگ توپ داخل کیسه را پیش‌بینی کند. اما از آنجایی که ذاتاً آدم بی‌هنریست، توانایی انجام این کار را ندارد. از این رو بر آن شده است که از شما کمک بگیرد و از شما می‌خواهد که رنگ توپ را فقط با دانستن $n$ و $m$ برای او پیش بینی کنید یا به او بگویید امکان پیش‌بینی وجود ندارد زیرا امکان دارد توپ باقی‌مانده سفید یا سیاه (بسته به ترتیب بیرون آوردن توپ‌ها) باشد تا او بتواند با انجام حرکات موزون مردم را سرگرم کند تا ناتوانی او در پیش‌بینی را فراموش کنند.

ورودی🔗

سطر اول ورودی شامل دو عدد $m$ و $n$ است که به ترتیب نشان دهنده‌ ی تعداد توپ‌های سیاه و تعداد توپ‌های سفید اند. $1 \le m,n \le 1000\ 000\ 000$

خروجی🔗

تنها سطر خروجی باید شامل یک کلمه باشد:

$white$ : به معنای اینکه توپ آخر سفید است.
$black$ : به معنای اینکه توپ آخر سیاه است.
$no prediction$ : به معنای اینکه امکان پیش‌بینی وجود ندارد.

مثال🔗

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

2 2

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

white

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

3 6

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

black

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- زرافه به تازگی تعدادی از زبان های بیگانگان (موجودات فضایی!) را کشف کردەاست. هر یک از زبان ها دارای یک الفبا بوده و هر کدام از این الفباها دارای هزاران حرف هستند. در هر زبان نیز به صورت عجیبی همەی کلمات به یک اندازه هستند (تعداد حرف برابر دارند). بیگانگان دوست دارند که کلمات شان زیبا باشد؛ بدین معناکه برای $i$‐اُمین حرف از الفبای $n$ حرفی شان، چنانچه: $$2 \times i > n$$ آنگاه این حرف می تواند حرف آخر یک کلمه باشد یا جلوی این حرف، هر حرف دیگری (حتی خودش) قرار بگیرد. و اگر:$$ 2 \times i \le n $$ آنگاه این حرف نمی تواند آخر یک کلمه باشد و حرف بعدی آن نیز در کلمه می تواند حرف $j$-اُم باشد اگر و تنها اگر $$ 2 \times i \le j $$ حال زرافه می خواهد بداند در یک زبان با $n$ حرف الفبا که طول هر کلمەاش $m$ است، چند کلمەی مختلف وجود دارد؟ از آن جا که این عدد می تواند بسیار بزرگ باشد، باقی ماندەی این عدد بر ${10}^{8} + {7}$ را چاپ کنید. $$1 \le t \le 5 $$ $$ 1 \le n \le 10^5 $$ $$1 \le m \le 5*10^5 $$ # ورودی خط اول ورودی، مقدار $t$ نشان دهندەی تعداد سناریوهاست. در $t$ خط بعدی، در هر خط یک سناریو آمده که در آن دو عدد $n$ و $m$ با فاصله پشت سر هم آمدەاند. # خروجی برای هر سناریو، باقی ماندەی تعداد کلمات ممکن در آن زبان را بر ${10}^{8} + {7}$ بنویسید. # مثال ## ورودی نمونه ۱ 3 1 3 2 3 3 2 ## خروجی نمونه ۱ 1 3 6

زرافه

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

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

بیگانگان دوست دارند که کلمات شان زیبا باشد؛ بدین معناکه برای $i$ ‐اُمین حرف از الفبای $n$ حرفی شان، چنانچه: $2 \times i > n$ آنگاه این حرف می تواند حرف آخر یک کلمه باشد یا جلوی این حرف، هر حرف دیگری (حتی خودش) قرار بگیرد. و اگر: $2 \times i \le n$ آنگاه این حرف نمی تواند آخر یک کلمه باشد و حرف بعدی آن نیز در کلمه می تواند حرف $j$ -اُم باشد اگر و تنها اگر $2 \times i \le j$ حال زرافه می خواهد بداند در یک زبان با $n$ حرف الفبا که طول هر کلمەاش $m$ است، چند کلمەی مختلف وجود دارد؟
از آن جا که این عدد می تواند بسیار بزرگ باشد، باقی ماندەی این عدد بر ${10}^{8} + {7}$ را چاپ کنید.

$1 \le t \le 5$ $1 \le n \le 10^5$ $1 \le m \le 5*10^5$

ورودی🔗

خط اول ورودی، مقدار $t$ نشان دهندەی تعداد سناریوهاست.
در $t$ خط بعدی، در هر خط یک سناریو آمده که در آن دو عدد $n$ و $m$ با فاصله پشت سر هم آمدەاند.

خروجی🔗

برای هر سناریو، باقی ماندەی تعداد کلمات ممکن در آن زبان را بر ${10}^{8} + {7}$ بنویسید.

مثال🔗

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

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

1
3
6

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دزد با مهارت، باید بتواند خوب تمرکز کند. متاسفانه دزد با وجود تمام شایستگی‌هایش موفق نشد که از سد پلیس‌ها رد شود و به طبقه‌ی آخر برود. بنابراین او یک راه دیگر را برای رسیدن به طبقه‌ی آخر انتخاب کرده است. او می‌خواهد با استفاده از تمرکز ذهنی، به پرواز در آمده و به طبقه‌ی آخر برود. اما متاسفانه مسئله‌ای بدجور فکرش را مشغول کرده و به او اجازه‌ی تمرکز نمی‌دهد. او از شما می‌خواهد که این مسئله را برایش حل نمایید تا فکرش آزاد شود. مسئله این است: اعداد یک تا $n$ بدون تکرار و به ترتیب دلخواه در یک ردیف نوشته‌ شده‌اند. به این ردیف به ترتیب دلخواه از اعداد، جایگشت می‌گوییم. برای مثال 5،6،4،1،3،2 یک جایگشت شش تایی است. پس ما یک جایگشت داریم. حالا از روی این جایگشت بدین گونه یک گراف می‌سازیم: اگر جایگشت را بصورت $p_1, p_2, ..., p_n$ نشان دهیم و راس های گراف ما با اعداد ۱ تا $n$ شماره گذاری شده باشند، یالی بین راس شماره $i$ و راس شماره $j$ وجود دارد اگر و تنها اگر $i < j$ و $p_i > p_j$. برای مثال اگر جایگشت ما 2،3،1 باشد، در گراف متناظر، راس شماره‌ی سه به دو راس دیگر متصل است ولی راس شماره‌ی دو به راس شماره‌ی یک متصل نیست. حالا سوال این است که این گراف چند مولفه‌ی همبندی دارد. (برای توضیحات بیشتر راجع به گراف و مولفه همبندی، [اینجا](https://fa.wikipedia.org/wiki/%D9%85%D8%A4%D9%84%D9%81%D9%87_%D9%87%D9%85%D8%A8%D9%86%D8%AF%DB%8C) را ببینید.) # ورودی در سطر اول ورودی $n$ آمده است که نمایانگر تعداد اعداد در جایگشت است. در سطر بعدی $n$ عدد آمده است که جایگشت را نشان می‌دهند. $i$مین عدد از این اعداد نمایانگر $p_i$ است. این اعداد، عددهای 1 تا $n$ هستند که به ترتیب دلخواه کنار هم چیده شده‌اند و هیچ عددی در این سطر دوبار نیامده است. $$ 1 \le n \le 1\ 000\ 000 $$ # خروجی در تنها سطر خروجی تعداد مولفه‌های همبندی گراف ساخته شده با جایگشت را خروجی دهید. # مثال ## ورودی نمونه ``` 6 3 2 4 1 6 5 ``` ## خروجی نمونه ``` 2 ``` توضیح: یال‌ها در گراف ساخته شده بین راس‌های زیر هستند: یک و دو، چهار و یک، دو و چهار، سه و چهار و پنج و شش. که باعث به وجود آمدن دو مولفه همبندی می‌شود که مولفه‌ی اول شامل راس‌های شماره‌ی 1 و 2 و 3 و 4 و مولفه‌ی دیگر شامل راس‌های 5 و 6 می‌باشد.

دزد و تمرکز

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

دزد با مهارت، باید بتواند خوب تمرکز کند. متاسفانه دزد با وجود تمام شایستگی‌هایش موفق نشد که از سد پلیس‌ها رد شود و به طبقه‌ی آخر برود. بنابراین او یک راه دیگر را برای رسیدن به طبقه‌ی آخر انتخاب کرده است. او می‌خواهد با استفاده از تمرکز ذهنی، به پرواز در آمده و به طبقه‌ی آخر برود. اما متاسفانه مسئله‌ای بدجور فکرش را مشغول کرده و به او اجازه‌ی تمرکز نمی‌دهد. او از شما می‌خواهد که این مسئله را برایش حل نمایید تا فکرش آزاد شود. مسئله این است:

اعداد یک تا $n$ بدون تکرار و به ترتیب دلخواه در یک ردیف نوشته‌ شده‌اند. به این ردیف به ترتیب دلخواه از اعداد، جایگشت می‌گوییم. برای مثال 5،6،4،1،3،2 یک جایگشت شش تایی است. پس ما یک جایگشت داریم. حالا از روی این جایگشت بدین گونه یک گراف می‌سازیم:

اگر جایگشت را بصورت $p_1, p_2, ..., p_n$ نشان دهیم و راس های گراف ما با اعداد ۱ تا $n$ شماره گذاری شده باشند، یالی بین راس شماره $i$ و راس شماره $j$ وجود دارد اگر و تنها اگر $i < j$ و $p_i > p_j$ .

برای مثال اگر جایگشت ما 2،3،1 باشد، در گراف متناظر، راس شماره‌ی سه به دو راس دیگر متصل است ولی راس شماره‌ی دو به راس شماره‌ی یک متصل نیست.

حالا سوال این است که این گراف چند مولفه‌ی همبندی دارد. (برای توضیحات بیشتر راجع به گراف و مولفه همبندی، اینجا را ببینید.)

ورودی🔗

در سطر اول ورودی $n$ آمده است که نمایانگر تعداد اعداد در جایگشت است. در سطر بعدی $n$ عدد آمده است که جایگشت را نشان می‌دهند. $i$ مین عدد از این اعداد نمایانگر $p_i$ است. این اعداد، عددهای 1 تا $n$ هستند که به ترتیب دلخواه کنار هم چیده شده‌اند و هیچ عددی در این سطر دوبار نیامده است.

$1 \le n \le 1\ 000\ 000$

خروجی🔗

در تنها سطر خروجی تعداد مولفه‌های همبندی گراف ساخته شده با جایگشت را خروجی دهید.

مثال🔗

ورودی نمونه🔗

6
3 2 4 1 6 5

خروجی نمونه🔗

توضیح:

یال‌ها در گراف ساخته شده بین راس‌های زیر هستند:

یک و دو، چهار و یک، دو و چهار، سه و چهار و پنج و شش.

که باعث به وجود آمدن دو مولفه همبندی می‌شود که مولفه‌ی اول شامل راس‌های شماره‌ی 1 و 2 و 3 و 4 و مولفه‌ی دیگر شامل راس‌های 5 و 6 می‌باشد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دیروز، مرحلەی نهایی مسابقات هوش مصنوعی شریف (Sharif AI Challenge) برگزار شد و برندگان و هم چنین رتبەی افراد شرکت کننده در این مسابقه اعلام گردید. در این چلنج $n$ تیم شرکت کرده بودند که هر تیم شمارەای بین ١ تا $n$ برحسب خفن بودن شون در مرحلەی انتخابی دریافت کرد. در آخر نیز تیم $p_1$ رنک اول، تیم $p_2$ رتبەی دوم، ... و تیم $p_n$ رتبەی $n$‐اُم راکسب کردند. (به عبارت دیگر $p$ جایگشتی از ١ تا $n$ می باشد.) لیتی پس از این که فهمید جزء سه نفر اول نشده، در اعتراض به نتایج غیرمنصفانەی این مسابقات در گفت وگو با حمید معصومی نژاد، خبرنگار اعزامی صداوسیمای جمهوری اسلامی ایران، رُم اعلام کرد که نتیجەی این مسابقات $k$‐عادلانه نیست! یک جایگشت را $k$‐عادلانه گویند هرگاه برای هر $i$ داشته باشیم: $$k \ge \, \mid i - p_i \mid $$ برگزارکنندگان این برنامه برای بیرون آمدن از زیر ذرەبین، معاملەای با لیتی کردند. اگر به ازای $k$ی که آن ها به لیتی می دهند، او تعداد تمام جایگشت های $k$‐عادلانەی ممکن را به آن ها بگوید، او را برندەی بلامنازع این سری از مسابقات اعلام می کنند.(انقدرکه این سؤال سخته!) لیتی دست به دامان شما شدەاست تا به او در پیداکردن جواب این مسئلەی تیم اجرایی کمک کنید. # ورودی در ورودی تنها دو عدد $n$ و $k$ می آید. $$ 1 \le n \le 100$$ $$ 1 \le k \le 6$$ # خروجی در خروجی، باقیمانده تعداد جایگشت های $k$‐عادلانه را بر ${10}^{9} + {7}$ چاپ می کنید. # مثال ## ورودی نمونه ۱ 10 3 ## خروجی نمونه ۱ 19708

شریف ای‌آی چلنج

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

دیروز، مرحلەی نهایی مسابقات هوش مصنوعی شریف (Sharif AI Challenge) برگزار شد و برندگان و هم چنین رتبەی افراد شرکت کننده در این مسابقه اعلام گردید. در این چلنج $n$ تیم شرکت کرده بودند که هر تیم شمارەای بین ١ تا $n$ برحسب خفن بودن شون در مرحلەی انتخابی دریافت کرد.
در آخر نیز تیم $p_1$ رنک اول، تیم $p_2$ رتبەی دوم، ... و تیم $p_n$ رتبەی $n$ ‐اُم راکسب کردند. (به عبارت دیگر $p$ جایگشتی از ١ تا $n$ می باشد.)

لیتی پس از این که فهمید جزء سه نفر اول نشده، در اعتراض به نتایج غیرمنصفانەی این مسابقات در گفت وگو با حمید معصومی نژاد، خبرنگار اعزامی صداوسیمای جمهوری اسلامی ایران، رُم اعلام کرد که نتیجەی این مسابقات $k$ ‐عادلانه نیست!

یک جایگشت را $k$ ‐عادلانه گویند هرگاه برای هر $i$ داشته باشیم: $k \ge \, \mid i - p_i \mid$ برگزارکنندگان این برنامه برای بیرون آمدن از زیر ذرەبین، معاملەای با لیتی کردند. اگر به ازای $k$ ی که آن ها به لیتی می دهند، او تعداد تمام جایگشت های $k$ ‐عادلانەی ممکن را به آن ها بگوید، او را برندەی بلامنازع این سری از مسابقات اعلام می کنند.(انقدرکه این سؤال سخته!)

لیتی دست به دامان شما شدەاست تا به او در پیداکردن جواب این مسئلەی تیم اجرایی کمک کنید.

ورودی🔗

در ورودی تنها دو عدد $n$ و $k$ می آید.
$1 \le n \le 100$ $1 \le k \le 6$

خروجی🔗

در خروجی، باقیمانده تعداد جایگشت های $k$ ‐عادلانه را بر ${10}^{9} + {7}$ چاپ می کنید.

مثال🔗

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

10 3