+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- در شرکت کوئرا **۳ کیک هم اندازه** دایره‌ای برای تولد باقر خریداری شده است. خانم عبادی می‌تواند یک کیک را: + به صورت کامل به ۱ نفر بدهد. + دو قسمت کند و به ۲ نفر بدهد. + چهار قسمت کند و به ۴ نفر بدهد. توجه کنید خانم عبادی، **برای هر کیک، دقیقاً یکی از این سه عملیات** بالا را می‌تواند انجام دهد. برای مثال نمی‌توان یک نصفه کیک را مجدداً به دو قسمت برابر تقسیم کرد. در روز تولد باقر $n$ نفر در شرکت حضور خواهند داشت. به خانم عبادی کمک کنید و بگویید آیا می‌تواند روی هر کدام از این سه کیک یکی از عملیات‌های بالا را انجام دهد به طوری که در نهایت به همه این $n$ نفر **مقدار برابری** کیک برسد یا نه. # ورودی در تنها سطر ورودی عدد صحیح و مثبت $n$ داده می‌شود. $$1 \leq n \leq 12$$ # خروجی در تنها سطر خروجی در صورتی که چنین تقسیم کردنی ممکن است `YES` و در غیراینصورت `NO` را چاپ کنید. **توجه کنید سیستم داوری به بزرگ و کوچک بودن حروف حساس است.** # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` YES ``` هر سه کیک را به یک نفر می‌دهد. پس این کار شدنی است. ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` YES ``` کیک اول را به نفر اول و کیک دوم را به نفر دوم می‌دهیم. کیک سوم را هم نصف می‌کنیم و نیمی از آن را به نفر اول و نیم دیگر را به نفر دوم می‌دهیم. ## ورودی نمونه ۳ ``` 3 ``` ## خروجی نمونه ۳ ``` YES ``` سه کیک داریم و به هر کدام یک کیک می‌دهیم. ## ورودی نمونه ۴ ``` 11 ``` ## خروجی نمونه ۴ ``` NO ``` با هر تقسیم بندی با قواعد بالا انجام این کار شدنی نیست.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- امیرحسین دستور ساخت یک رشته افسانه‌ای را پیدا کرده‌است. برای ساخت این رشته باید مقدار $n$ را انتخاب کنیم و رشته $s_n$ را به این روش تولید کنیم: اگر $n = 1$ آنگاه: $$s_n = "1"$$ اگر $n > 1$ آنگاه: $$s_n = s_{n - 1} + "n" + s_{n - 1}$$ منظور از $a + b$ برای دو رشته $a$ و $b$، یعنی رشته‌ای که از چسابندن $a$ در سمت چپ $b$ بدست می‌آید. منظور از $"n"$ نمایش عدد صحیح $n$ به صورت یک رشته است. پس با توجه به تعریف بالا داریم: $$s_1 = "1"$$ $$s_2 = "121"$$ $$s_3 = "1213121"$$ $$...$$ حال از شما می‌خواهیم **مجموع ارقام** نوشته شده در رشته‌ی $s_n$ را چاپ کنید. چون ممکن است این مقدار خیلی بزرگ باشد، باقی‌مانده آن را بر $10^9+7$ محاسبه کنید. # ورودی در تنها سطر اول ورودی عدد صحیح $n$ آمده است. $$1 \leq n \leq 100$$ # خروجی در تنها سطر خروجی باقی‌مانده مجموع ارقام نوشته شده در رشته‌ی $s_n$، بر $10^9+7$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` 1 ``` رشته $s_1 = "1"$ است پس مجموع ارقام آن برابر $1$ است. ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` 4 ``` رشته $s_2 = "121"$ است پس مجموع ارقام آن برابر $1 + 2 + 1 = 4$ است. ## ورودی نمونه ۳ ``` 3 ``` ## خروجی نمونه ۳ ``` 11 ``` رشته $s_3 = "1213121"$ است پس مجموع ارقام آن برابر $1 + 2 + 1 + 3 + 1 + 2 + 1 = 11$ است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- باقر می‌خواهد $n$ نامه برای $m$ شرکت مختلف بفرستد. نام این شرکت‌ها را با اعداد $1, 2, \dots, m \,$ نمایش می‌دهیم. باید نامه‌ی اول به شرکت $l_1$، نامه دوم به شرکت $l_2$ و... نامه $n$ام به شرکت $l_n$ ارسال شود. به عبارت دیگر نامه $i$ام ($1 \leq i \leq n$) باید به شرکت $l_i$ ($1 \leq l_i \leq m$) ارسال شود. باقر برای ارسال این نامه‌ها، $n$ پاکت تهیه می‌کند که روی پاکت $i$ام نشانی شرکت $l_i$ نوشته شده است. باقر به مهدی می‌گوید که نامه $i$ام را در پاکت $i$ام قرار بده و در صندوق پست بنداز. اما مهدی می‌خواهد این فرمان را به درستی انجام ندهد و کار را اساسی خراب کند. به همین دلیل تصمیم دارد طوری نامه‌ها را در پاکت‌ها قرار دهد که در هر پاکت دقیقاً یک نامه قرار بگیرد ولی **هیچ شرکتی نامه مربوط به خودش را دریافت نکند**. به مهدی کمک کنید تا بررسی کند آیا انجام چنین کاری شدنی است یا نه. # ورودی در سطر اول ورودی دو عدد صحیح و مثبت $n$ و $m$ که با فاصله از هم جدا شده‌اند، داده می‌شود. $$1 \leq m \leq n \leq 100 \, 000$$ در سطر دوم ورودی $n$ عدد صحیح و مثبت $l_1, l_2, \dots, l_n \,$ که با فاصله از هم جدا شده است آمده و شرکت مقصد نامه $i$ام را نشان می‌دهد. $$1 \leq l_i \leq m$$ تضمین می‌شود که هر کدام از اعداد $1, 2, \dots, m \,$ حداقل یکبار در این دنباله ظاهر شده‌اند. # خروجی در تنها سطر خروجی در صورتی که می‌توان طوری نامه‌ها را در پاکت‌ها گذاشت به‌طوری که هیچ‌نامه‌ای به شرکت مربوط به خودش نرسد، `YES` و در غیر این صورت `NO` چاپ کنید. **توجه کنید سیستم داوری به بزرگ و کوچک بودن حروف حساس است.** # مثال ## ورودی نمونه ۱ ``` 3 1 1 1 1 ``` ## خروجی نمونه ۱ ``` NO ``` همه نامه‌ها به شرکت ‍‍۱ است پس همه پاکت‌ها هم آدرس شرکت ۱ را دارند پس هر جایگشتی از نامه‌ها را که در پاکت‌ها قرار دهیم، همه نامه‌ها به شرکت ۱ می‌رسد و مهدی به هدفش نمی‌رسد. ## ورودی نمونه ۲ ``` 4 4 4 1 2 3 ``` ## خروجی نمونه ۲ ``` YES ``` چهار نامه برای شرکت‌های ۱ و ۲ و ۳ و ۴ و چهار پاکت با آدرس شرکت‌های ۱ و ۲ و ۳ و ۴ داریم. نامه شرکت ۱ را در پاکت شرکت ۲ و نامه شرکت ۲ را در پاکت شرکت ۱ قرار می‌دهیم. همچنین نامه شرکت ۳ را در پاکت شرکت ۴ و نامه شرکت ۴ را در پاکت شرکت ۳ قرار می‌دهیم. به این ترتیب هیچ‌نامه‌ای به شرکت مربوط به خود نمی‌رسد و مهدی به هدفش می‌رسد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک رشته از حروف کوچک انگلیسی به نام $s = s_1s_2\dots s_n \,$ داریم. منظور از یک «شیفت $s$» یعنی انتقال دادن $k$ حرف اول این رشته به آخر آن. ($ 1 \leq k \leq n \,$) به عبارت دیگر یک شیفت $s$، یک رشته به صورت زیر است:‌ $$s_{k + 1} \dots s_n s_1 s_2 \dots s_k$$ حال از شما می‌خواهیم با داشتن رشته $s$، رشته‌ای از این $n$ شیفت را پیدا کنید که در **ترتیب الفبایی کمینه** باشد. در ترتیب الفبایی، رشته $a$ از رشته $b$ کمتر است اگر اولین کاراکتر $a$ که با $b$ فرق دارد، در ترتیب الفبای انگلیسی زودتر آمده باشد. # ورودی در تنها سطر ورودی یک رشته از حروف کوچک انگلیسی مثل $s$ آمده است. $$1 \leq |s| \leq 100 \, 000$$ منظور از $|s|$ طول رشته $s$ است. # خروجی در تنها سطر خروجی رشته‌ای از حروف کوچک انگلیسی را چاپ کنید که شیفتی از $s$ بوده و به صورت الفبایی کمینه باشد. # مثال ## ورودی نمونه ۱ ``` nima ``` ## خروجی نمونه ۱ ``` anim ``` شیفت‌های `nima` عبارت است از `iman`، `mani`، `anim` و `nima` که رشته‌ای که در ترتیب الفبایی بین این ۴ رشته کوچک‌ترین است `anim` خواهد بود. ## ورودی نمونه ۲ ``` acabd ``` ## خروجی نمونه ۲ ``` abdac ``` شیفت‌های `acabd` عبارت است از `cabda`، `abdac`، `bdaca`، `dacab` و `acabd` است که رشته‌ای که در ترتیب الفبایی بین این ۵ رشته کوچک‌ترین است `abdac` خواهد بود.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به یک رشته از `)` و `(` یک «پرانتزگذاری معتبر» می‌گوییم اگر برای هر پرانتز باز بتوان یک پرانتز بسته متناظر کرد به طوری که رشته بین این دو پرانتز تشکیل یک پرانتزگذاری معتبر دهد و با حذف این بازه رشته باقی‌مانده پرانتزگذاری معتبر باشد. به یک پرانتز گذاری «$k$-معتبر» می‌گوییم اگر با اضافه کردن $k$ پرانتز باز به ابتدای رشته و $k$ پرانتز بسته در انتهای آن، پرانتز گذاری معتبر شود. تعداد رشته‌هایی را بیاید که طول آن $2n$ بوده و $k$-معتبر باشد. چون تعداد این رشته خیلی زیاد است باقی‌مانده پاسخ مسئله را به $10^9 + 7$ چاپ کنید. # ورودی در سطر اول ورودی عدد صحیح و مثبت $t$ داده می‌شود و در $t$ سطر بعدی هر کدام دو عدد $n$ و $k$ داده می شود. $$1 \le t \le 10^5$$ $$0 \le k \le 10^6$$ $$1 \le n \le 10^6$$ # خروجی خروجی شامل $t$ سطر است که در هر سطر تعداد رشته های به طول $2n$ که $k$-معتبر باشد را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 2 1 4 2 5 3 ``` ## خروجی نمونه ۱ ``` 5 62 242 ```