لبویِ بنده‌خدا

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

لبو که دیگر تحمّل دوریِ یار را ندارد، شروع به پرپر کردن یکی از گل‌هایی که برای یار خریده است، می‌کند.

او گلبرگ‌ها را می‌چیند و به شیوه‌ی زیر با خود زمزمه می‌کند:

گلبرگ اوّل: یکی دوسِش دارم.
گلبرگ دوّم: دوتا دوسَم داره.
گلبرگ سوّم: سه‌تا دوسِش دارم.
گلبرگ چهارم: چهار‌تا دوسَم داره.
و ...

اگر گل در ابتدا $n$ گلبرگ داشته‌باشد، لبو یار را چندتا دوست دارد؟ (مجموعِ «دوسِش دارم‌»ها) و همچنین یار لبو را چندتا دوست دارد؟ (مجموعِ «دوسم داره»ها)

ورودی🔗

در تنها خط ورودی عدد $n$ که تعداد گلبرگ‌های گل آمده‌است. $1 \leq n \leq 1000$

خروجی🔗

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

خط اوّل: مقداری که لبو یار را دوست دارد.

خط دوّم: مقداری که یار لبو را دوست دارد.

مثال🔗

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

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

4
2

توضیح نمونه ۱:گلبرگ‌ها به صورت زیر چیده می‌شوند:

گلبرگ اوّل: یکی دوسش دارم.
گلبرگ دوّم: دوتا دوسم داره.
گلبرگ سوّم: سه‌تا دوسش دارم.

پس لبو $1+3=4$ تا یار را دوست دارد و یار $2$ تا لبو را دوست دارد.

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

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

625
650

کادو

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

لبو که به بی‌ثمر بودنِ گل خریدن و گل پرپر کردن پی برده است؛ تصمیم گرفته تا برای یار کادوهای بهتری بخرد.

لبو می‌داند یار شیفته‌ی دنباله‌های « $n$ سام» است.

دنباله‌ی $n$ سام دارای ویژگی‌های زیر است:

صعودی است.
مجموع اعداد دنباله برابر $n$ است.
اختلاف هر دو عدد دنباله حدّاکثر برابر $1$ می‌باشد.

چون لبو خیلی دست‌‌ودل‌باز است، می‌خواهد از هر دنباله‌ی $n$ سام یکی برای یار بخرد، امّا قبل از هرچیز می‌خواهد تعداد این دنباله‌ها را بداند تا پول‌هایش را جمع کند. به لبو کمک کنید.

ورودی🔗

در تنها خط ورودی عدد $n$ آمده‌است. $1\leq n \leq10^9$

خروجی🔗

باقی‌مانده‌ی تعداد دنباله‌های $n$ سام بر $10^9+7$ را در خروجی چاپ کنید.

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗

توضیح نمونه: دنباله‌های $3$ سام در زیر نمایش داده شده‌اند.

$1, 1, 1$
$1, 2$
$3$

+ محدودیتِ زمان: ۱ ثانیه + محدودیتِ حافظه: ۲۵۶ مگابایت ---------- یار در یک جدول $n$ در $n$ که دارای $n\times{}n$ اتاق است، زندگی می‌کند. سطرهای خانه از بالا به پایین و ستون‌ها از چپ به راست با $1, 2, 3, ..., n$ شماره‌گذاری شده‌اند. یار در اتاق سطر$i$ و ستون$j$ این جدول ایستاده است. لبو می‌خواهد وارد خانه‌ی یار شود و بعد از گل‌باران کردنِ خانه، کادوهایی که برای یار خریده‌است را به او تقدیم کند. لبو ابتدا روی اتاق سطر $1$ و ستون $1$ خانه ایستاده‌است و جهت حرکت او به سمت راست می‌باشد. دور تا دور جدول با دیوار پوشانده شده و بعضی از اتاق های خانه پر از گل سرخ هستند و لبو چون نمی‌خواهد به گل‌ها آسیبی بزند وارد این اتاق‌ها نمی‌شود. اگر لبو به دیوار بخورد یا جلوی او اتاقی پر از گل باشد جهت حرکتش را $90$ درجه ساعتگرد تغییر می‌دهد وگرنه به اتاق جلوییش می‌رود اما اگر هر چهارطرف لبو دیوار یا پر از گل‌سرخ باشد، لبو متوقف می‌شود. هم‌چنین وقتی لبو می‌خواهد از اتاقی خارج شود، آن اتاق را پر از گل سرخ می‌کند. تعداد اتاق‌هایی که در ابتدا پر از گل سرخ هستند حداقل چندتا باشد تا لبو در نهایت در اتاقی که یار آنجاست **متوقف** شود؟ # ورودی در تنها خط ورودی سه عدد $n$ و $i$ و $j$ آمده است. $$1 \leq i, j \leq n \leq 10^{12}$$ # خروجی در خروجی یک عدد چاپ کنید که برابر تعداد خانه‌هایی است که از ابتدا باید پر از گل باشند. # مثال ## ورودی نمونه‌ ``` 3 2 3 ``` ## خروجی نمونه‌ ``` 2 ``` **توضیح نمونه: ** ![توضیح تصویر](http://s9.picofile.com/file/8314364792/photo_2017_12_16_01_32_33.jpg)

لبو و گل‌های سرخ

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

یار در یک جدول $n$ در $n$ که دارای $n\times{}n$ اتاق است، زندگی می‌کند. سطرهای خانه از بالا به پایین و ستون‌ها از چپ به راست با $1, 2, 3, ..., n$ شماره‌گذاری شده‌اند. یار در اتاق سطر $i$ و ستون $j$ این جدول ایستاده است.

لبو می‌خواهد وارد خانه‌ی یار شود و بعد از گل‌باران کردنِ خانه، کادوهایی که برای یار خریده‌است را به او تقدیم کند.

لبو ابتدا روی اتاق سطر $1$ و ستون $1$ خانه ایستاده‌است و جهت حرکت او به سمت راست می‌باشد.

دور تا دور جدول با دیوار پوشانده شده و بعضی از اتاق های خانه پر از گل سرخ هستند و لبو چون نمی‌خواهد به گل‌ها آسیبی بزند وارد این اتاق‌ها نمی‌شود. اگر لبو به دیوار بخورد یا جلوی او اتاقی پر از گل باشد جهت حرکتش را $90$ درجه ساعتگرد تغییر می‌دهد وگرنه به اتاق جلوییش می‌رود اما اگر هر چهارطرف لبو دیوار یا پر از گل‌سرخ باشد، لبو متوقف می‌شود.

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

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

ورودی🔗

در تنها خط ورودی سه عدد $n$ و $i$ و $j$ آمده است. $1 \leq i, j \leq n \leq 10^{12}$

خروجی🔗

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

مثال🔗

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

3 2 3

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

*توضیح نمونه: * توضیح تصویر

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به لبو خبر رسیده که یار کادوهای لبو را گرفته و فِلِنگ را بسته‌‌است. (البته هنوز از کشور خارج نشده‌است.) کشور لبواینا $n$ شهر دارد و بین بعضی از شهرهای آن جادّه‌ی دوطرفه وجود دارد. در این کشور برای عبور از هر جادّه‌‌ تعدادی مجوز نیاز است. اگر طول جادّه‌ای $l$ باشد و در نمایش دودویی عدد $l$، رقم مربوط به $2^i$ برابر $1$ باشد، برای عبور از این جادّه داشتن مجوز نوع $i$ الزامی است. بهای مجوز نوع $i$ برابر $2^i$ تومان است. اگر لبو مجوز نوع $i$ را خریداری کند، برای عبور از هرجادّه‌ای می‌تواند از آن مجوز استفاده کند. از آنجا که لبو نمی‌داند یار به کدام شهر رفته‌است‌، حدّاقل بهایی که باید برای تهیّه‌ی مجوز بپردازد تا مطمئن باشد می‌تواند یار را پیدا کند چند تومان است؟ # ورودی در خط اوّل ورودی دو عدد $n$ و $m$، تعداد شهرهای کشور لبواینا و تعداد جادّ‌ه‌‌های کشور، آمده است. در$m$ خط بعد در هر خط سه عدد $u_i$ و $v_i$ و $w_i$ آمده‌است که مشخصّات جادّه‌ی $i$ اُم هستند. به این معنی که یک جادّه‌ی دوطرفه به طول $w_i$ بین شهر $u_i$ و $v_i$ وجود دارد. تضمین می‌شود بین هر دو شهر حداکثر یک جادّه وجود دارد و از هر شهری به هر شهر دیگر حداقل یک مسیر موجود است. $$1 \leq n,m \leq {5 \times{}10^5}$$ $$1 \leq u_i \ne v_i \leq n$$ $$1 \leq w_i \leq 10^9$$ # خروجی در خروجی یک عدد چاپ کنید که برابر حداقل بهایی است که لبو باید بپردازد تا از پیدا کردن یار مطمئن شود. # مثال ## ورودی نمونه ۱ ``` 3 3 1 2 4 2 3 2 3 1 1 ``` ## خروجی نمونه ۱ ``` 3 ``` **توضیح تمونه ۱:** کافی است لبو مجوز‌های نوع $0$ و نوع $1$ را خریداری کند. ## ورودی نمونه ۲ ``` 4 4 1 2 5 2 3 2 3 4 2 4 1 4 ``` ## خروجی نمونه ۲ ``` 6 ```

در جست‌وجوی یار

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

به لبو خبر رسیده که یار کادوهای لبو را گرفته و فِلِنگ را بسته‌‌است. (البته هنوز از کشور خارج نشده‌است.)

کشور لبواینا $n$ شهر دارد و بین بعضی از شهرهای آن جادّه‌ی دوطرفه وجود دارد.

در این کشور برای عبور از هر جادّه‌‌ تعدادی مجوز نیاز است. اگر طول جادّه‌ای $l$ باشد و در نمایش دودویی عدد $l$ ، رقم مربوط به $2^i$ برابر $1$ باشد، برای عبور از این جادّه داشتن مجوز نوع $i$ الزامی است. بهای مجوز نوع $i$ برابر $2^i$ تومان است. اگر لبو مجوز نوع $i$ را خریداری کند، برای عبور از هرجادّه‌ای می‌تواند از آن مجوز استفاده کند.

از آنجا که لبو نمی‌داند یار به کدام شهر رفته‌است‌، حدّاقل بهایی که باید برای تهیّه‌ی مجوز بپردازد تا مطمئن باشد می‌تواند یار را پیدا کند چند تومان است؟

ورودی🔗

در خط اوّل ورودی دو عدد $n$ و $m$ ، تعداد شهرهای کشور لبواینا و تعداد جادّ‌ه‌‌های کشور، آمده است.

در $m$ خط بعد در هر خط سه عدد $u_i$ و $v_i$ و $w_i$ آمده‌است که مشخصّات جادّه‌ی $i$ اُم هستند. به این معنی که یک جادّه‌ی دوطرفه به طول $w_i$ بین شهر $u_i$ و $v_i$ وجود دارد.

تضمین می‌شود بین هر دو شهر حداکثر یک جادّه وجود دارد و از هر شهری به هر شهر دیگر حداقل یک مسیر موجود است.

$1 \leq n,m \leq {5 \times{}10^5}$ $1 \leq u_i \ne v_i \leq n$ $1 \leq w_i \leq 10^9$

خروجی🔗

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

مثال🔗

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

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

توضیح تمونه ۱: کافی است لبو مجوز‌های نوع $0$ و نوع $1$ را خریداری کند.

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

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

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- لبو که از دنبال یار دویدن خسته شده، یک گوشه نشسته و بازی اصغر و حشمت را تماشا می‌کند. بازی به صورت زیر است: یک سبد با گنجایش $n$ توپ و یک تاس همگن $n$ وجهی با اعداد $1, 2, 3, ..., n$ داریم. (حقیقت این است که به ازای بعضی $n$ها تاس همگن وجود ندارد که ما به حقیقت کاری نداریم!) بازی با اصغر شروع و به نوبت انجام می‌شود. در اوّل بازی سبد خالی است. اصغر در نوبت خود تاس می‌ریزد و به اندازه‌ی عدد تاس در سبد توپ می‌اندازد. حشمت در نوبت خود تاس می‌اندازد و به اندازه‌ی عدد تاس از سبد توپ خارج می‌کند. در همین حین هربار که یکی از دو بازیکن تاس می‌اندازد؛ لبو عدد روی تاس را روی کاغذ یادداشت می‌کند تا به یادِ یار دنباله‌ای درست کند. اگر در نوبت اصغر عدد تاس بیشتر از گنجایش سبد در آن لحظه باشد(یعنی اصغر نتواند به اندازه‌ی عدد تاس در سبد توپ بیاندازد.) اصغر می‌بازد. اگر در نوبت حشمت عدد تاس بیشتر از توپ‌های موجود در سبد باشد(یعنی حشمت قادر به انجام حرکت نباشد.) حشمت می‌بازد. اگر یکی از دو بازیکن ببازد بازی تمام می‌شود. اگر طول دنباله‌ی لبو بعد از پایان بازی $t$ باشد؛ دنباله‌ی نهایی چند حالت مختلف می‌تواند داشته باشد؟ # ورودی در تنها خط ورودی دو عدد $n$ و $t$ آمده است. $$1 \leq n \leq 100$$ $$1 \leq t \leq 10^9$$ # خروجی در خروجی باقی‌مانده‌ی پاسخ مسئله بر $10^9 +7$ را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 3 ``` ## خروجی نمونه ۱ ``` 1 ``` **توضیح نمونه ۱:** تنها دنباله‌ی به طول $3$ که ممکن است لبو نوشته باشد $2, 1, 2$ است: 1. اصغر $2$ توپ داخل سبد می‌اندازد. 2. حشمت یکی از توپ‌ها را برمی‌دارد. 3. اصغر تاس می‌اندازد و عدد $2$ می‌آید امّا نمی‌تواند $2$ توپ در سبد بیاندازد چون $1$ توپ در سبد موجود است و سبد فقط به اندازه‌ی $1$ توپ دیگر جا دارد. پس بازی تمام می‌شود و دنباله‌ی یادداشت شده برابر $2, 1, 2$ است. ## ورودی نمونه ۲ ``` 36 198456974 ``` ## خروجی نمونه ۲ ``` 307142278 ```

لبوی خسته

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

لبو که از دنبال یار دویدن خسته شده، یک گوشه نشسته و بازی اصغر و حشمت را تماشا می‌کند.

بازی به صورت زیر است:

یک سبد با گنجایش $n$ توپ و یک تاس همگن $n$ وجهی با اعداد $1, 2, 3, ..., n$ داریم. (حقیقت این است که به ازای بعضی $n$ ها تاس همگن وجود ندارد که ما به حقیقت کاری نداریم!)

بازی با اصغر شروع و به نوبت انجام می‌شود. در اوّل بازی سبد خالی است.

اصغر در نوبت خود تاس می‌ریزد و به اندازه‌ی عدد تاس در سبد توپ می‌اندازد.

حشمت در نوبت خود تاس می‌اندازد و به اندازه‌ی عدد تاس از سبد توپ خارج می‌کند.

در همین حین هربار که یکی از دو بازیکن تاس می‌اندازد؛ لبو عدد روی تاس را روی کاغذ یادداشت می‌کند تا به یادِ یار دنباله‌ای درست کند.

اگر در نوبت اصغر عدد تاس بیشتر از گنجایش سبد در آن لحظه باشد(یعنی اصغر نتواند به اندازه‌ی عدد تاس در سبد توپ بیاندازد.) اصغر می‌بازد.

اگر در نوبت حشمت عدد تاس بیشتر از توپ‌های موجود در سبد باشد(یعنی حشمت قادر به انجام حرکت نباشد.) حشمت می‌بازد.

اگر یکی از دو بازیکن ببازد بازی تمام می‌شود.

اگر طول دنباله‌ی لبو بعد از پایان بازی $t$ باشد؛ دنباله‌ی نهایی چند حالت مختلف می‌تواند داشته باشد؟

ورودی🔗

در تنها خط ورودی دو عدد $n$ و $t$ آمده است. $1 \leq n \leq 100$ $1 \leq t \leq 10^9$

خروجی🔗

در خروجی باقی‌مانده‌ی پاسخ مسئله بر $10^9 +7$ را چاپ کنید.

مثال🔗

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

2 3

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

توضیح نمونه ۱: تنها دنباله‌ی به طول $3$ که ممکن است لبو نوشته باشد $2, 1, 2$ است:

اصغر $2$ توپ داخل سبد می‌اندازد.
حشمت یکی از توپ‌ها را برمی‌دارد.
اصغر تاس می‌اندازد و عدد $2$ می‌آید امّا نمی‌تواند $2$ توپ در سبد بیاندازد چون $1$ توپ در سبد موجود است و سبد فقط به اندازه‌ی $1$ توپ دیگر جا دارد.

پس بازی تمام می‌شود و دنباله‌ی یادداشت شده برابر $2, 1, 2$ است.

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

36 198456974

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

307142278

+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- لبو با دیدن بازی اصغر و حشمت، باز دلش هوایی شد و به هوای یار به خواب رفت! در این خوابِ رویایی یک فرد ناشناس $n$ تا از شماره موبایل‌های یار را به لبو داد. لبو ناگهان از خواب پرید ولی خوشبختانه شماره موبایل‌های یار در ذهنش مانده‌است. حال می‌خواهد طی یک عملیات $n$ روزه دلِ یار را به‌دست بیاورد. برای اینکار باید از فرایند «خودشیرین‌کُنی» استفاده کند. اگر لبو فرایند خودشیرین‌کُنی را در روز $i$اُم انجام دهد؛ باید به **تمام** شماره موبایل‌های$1$ تا $i$ یار، $sms$ خالی فرستاده و به یکی از شماره‌‌ موبایل‌های$1$ تا $i$، یک‌ $sms$ چاپلوسانه هم بفرستد. لبو می‌تواند فرایند خود شیرین کنی را هر‌چندبار که بخواهد در یک روز انجام دهد. (حتّی $0$ بار!!) اگر لبو طوری عمل کند که پس از روز $n$اُم، دقیقا $a_i$ تا $sms$ به شماره‌موبایل $i$اُم یار فرستاده باشد؛ دل یار را به دست می‌آورد. لبو به چند روش مختلف می‌تواند دل یار را به دست بیاورد؟ # ورودی در خط اول ورودی عدد $n$، تعداد شماره موبایل‌های یار، آمده‌است. در خط بعد $n$ عدد آمده‌ که عدد $i$اُم، $a_i$ است. $$ 1 \leq n \leq 1000$$ $$ 0 \leq a_i \leq 1000$$ $$ 0 \leq \sum_{i=1}^n a_i \leq 1000$$ # خروجی در تنها خط خروجی باقیمانده‌ی پاسخ مسئله بر $10^9+7$ را چاپ کنید. دقت کنید دو روش مختلف اند اگر $i$ای موجود باشد که تعداد فرآیند‌های خودشیرین‌کُنی انجام‌شده در روز $i$اُم در دو روش متمایز باشد **یا یکی از فرآیندهای خودشیرین کنی روز $i$ در روش اول با فرایند خودشیرین کنی متناظرش در روش دوم متفاوت باشد. دو فرایند خودشیرین کنی در یک روز متفاوتند اگر $sms$ چاپلوسانه به سیمکارت متفاوتی ارسال شود.** # مثال ## ورودی نمونه ۱ ``` 4 4 3 2 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 2 1 1 ``` ## خروجی نمونه ۲ ``` 0 ```

خواب شیرین

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

لبو با دیدن بازی اصغر و حشمت، باز دلش هوایی شد و به هوای یار به خواب رفت! در این خوابِ رویایی یک فرد ناشناس $n$ تا از شماره موبایل‌های یار را به لبو داد.

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

برای اینکار باید از فرایند «خودشیرین‌کُنی» استفاده کند. اگر لبو فرایند خودشیرین‌کُنی را در روز $i$ اُم انجام دهد؛ باید به تمام شماره موبایل‌های $1$ تا $i$ یار، $sms$ خالی فرستاده و به یکی از شماره‌‌ موبایل‌های $1$ تا $i$ ، یک‌ $sms$ چاپلوسانه هم بفرستد.

لبو می‌تواند فرایند خود شیرین کنی را هر‌چندبار که بخواهد در یک روز انجام دهد. (حتّی $0$ بار!!)

اگر لبو طوری عمل کند که پس از روز $n$ اُم، دقیقا $a_i$ تا $sms$ به شماره‌موبایل $i$ اُم یار فرستاده باشد؛ دل یار را به دست می‌آورد.

لبو به چند روش مختلف می‌تواند دل یار را به دست بیاورد؟

ورودی🔗

در خط اول ورودی عدد $n$ ، تعداد شماره موبایل‌های یار، آمده‌است.

در خط بعد $n$ عدد آمده‌ که عدد $i$ اُم، $a_i$ است.

$1 \leq n \leq 1000$ $0 \leq a_i \leq 1000$ $0 \leq \sum_{i=1}^n a_i \leq 1000$

خروجی🔗

در تنها خط خروجی باقیمانده‌ی پاسخ مسئله بر $10^9+7$ را چاپ کنید.

دقت کنید دو روش مختلف اند اگر $i$ ای موجود باشد که تعداد فرآیند‌های خودشیرین‌کُنی انجام‌شده در روز $i$ اُم در دو روش متمایز باشد یا یکی از فرآیندهای خودشیرین کنی روز $i$ در روش اول با فرایند خودشیرین کنی متناظرش در روش دوم متفاوت باشد. دو فرایند خودشیرین کنی در یک روز متفاوتند اگر $sms$ چاپلوسانه به سیمکارت متفاوتی ارسال شود.

مثال🔗

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

4
4 3 2 1

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

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

2
1 1

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بالأخره پس از دردسرهای فراوان لبو و یار به هم رسیدند! حال مراسم ازدواج آن‌هاست! در این مراسم فردی از خانواده‌ی لبو در مقابل فردی از خانواده‌ی یار ایستاده و بازی دونفره و نوبتی زیر را باهم انجام می‌دهند: در این بازی $n$ کیسه‌ی نُقل با شماره‌های $1, 2, 3, ..., n$ داریم و خانواده‌ی لبو شروع کننده‌ی بازی است. در هر مرحله فردی که نوبت اوست باید از دقیقاً یکی از کیسه‌هایی که خالی نیستند حدّاقل یک نقل برداشته و بر سر عروس و داماد بریزد. کسی که نتواند نقلی بردارد می‌بازد و بازی تمام می‌شود. لبو وظیفه‌ی قرار دادن نقل در کیسه‌ها را قبل از شروع بازی دارد، امّا برای اینکه کیسه‌ها پاره نشوند در هر کیسه حدّاکثر $m$ نقل قرار می‌دهد. (لبو می‎تواند هیچ نقلی در کیسه قرار ندهد.) چون لبو شیفته‌ی یار است، می‌خواهد تعداد حالت‌های مختلف از قرار دادن نقل‌ها در کیسه‌ها را بداند به طوری‌که اگر دو بازیکن به بهترین نحو ممکن بازی کنند خانواده‌ی یار برنده شود. # ورودی در خط اول ورودی عدد $t$، تعداد تست‌ها، آمده‌است. در $t$ خط بعدی در هر خط دو عدد $n_i$ و $m_i$ که با فاصله از هم جدا شده‌اند آمده‌است. $$1 \leq t \leq 1000$$ $$1 \leq n_i, m_i \leq 10^{18}$$ # خروجی خروجی شامل $t$ خط است. در خط $i$اُم با توجه به $n_i$ و $m_i$ داده شده، باقی‌مانده ی پاسخ مسئله بر $10^9+7$ را چاپ کنید. دقت کنید دوحالت از قرار دادن نقل‌ها در کیسه‌ها متفاوت اند اگر عدد $i$ موجود باشد که تعداد نقل‌های کیسه‌ی $i$ در دو حالت متمایز باشد. ## ورودی نمونه ``` 4 2 1 1 6 3 2 2 9 ``` ## خروجی نمونه ``` 2 1 7 10 ``` **توضیح نمونه:** حالات مناسب برای برنده شدن خانواده‎ی یار برای هر کدام از 4 حدس لبو در زیر آمده‎است: >**تست ۱:** >$$(0, 0), (1, 1)$$ > >**تست ۲:** >$$(0)$$ > >**تست ۳:** >$$(0, 0, 0), (0, 1, 1), (0, 2, 2), (1, 0, 1), (1, 1, 0), (2, 0, 2), (2, 2, 0)$$ > >**تست ۴:** >$$(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)$$

خانه‌ی بخت

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

بالأخره پس از دردسرهای فراوان لبو و یار به هم رسیدند! حال مراسم ازدواج آن‌هاست!

در این مراسم فردی از خانواده‌ی لبو در مقابل فردی از خانواده‌ی یار ایستاده و بازی دونفره و نوبتی زیر را باهم انجام می‌دهند:

در این بازی $n$ کیسه‌ی نُقل با شماره‌های $1, 2, 3, ..., n$ داریم و خانواده‌ی لبو شروع کننده‌ی بازی است.

در هر مرحله فردی که نوبت اوست باید از دقیقاً یکی از کیسه‌هایی که خالی نیستند حدّاقل یک نقل برداشته و بر سر عروس و داماد بریزد. کسی که نتواند نقلی بردارد می‌بازد و بازی تمام می‌شود.

لبو وظیفه‌ی قرار دادن نقل در کیسه‌ها را قبل از شروع بازی دارد، امّا برای اینکه کیسه‌ها پاره نشوند در هر کیسه حدّاکثر $m$ نقل قرار می‌دهد. (لبو می‎تواند هیچ نقلی در کیسه قرار ندهد.)

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

ورودی🔗

در خط اول ورودی عدد $t$ ، تعداد تست‌ها، آمده‌است.

در $t$ خط بعدی در هر خط دو عدد $n_i$ و $m_i$ که با فاصله از هم جدا شده‌اند آمده‌است.

$1 \leq t \leq 1000$ $1 \leq n_i, m_i \leq 10^{18}$

خروجی🔗

خروجی شامل $t$ خط است. در خط $i$ اُم با توجه به $n_i$ و $m_i$ داده شده، باقی‌مانده ی پاسخ مسئله بر $10^9+7$ را چاپ کنید.

دقت کنید دوحالت از قرار دادن نقل‌ها در کیسه‌ها متفاوت اند اگر عدد $i$ موجود باشد که تعداد نقل‌های کیسه‌ی $i$ در دو حالت متمایز باشد.

ورودی نمونه🔗

خروجی نمونه🔗

توضیح نمونه: حالات مناسب برای برنده شدن خانواده‎ی یار برای هر کدام از 4 حدس لبو در زیر آمده‎است:

تست ۱: $(0, 0), (1, 1)$

تست ۲: $(0)$

تست ۳: $(0, 0, 0), (0, 1, 1), (0, 2, 2), (1, 0, 1), (1, 1, 0), (2, 0, 2), (2, 2, 0)$

تست ۴: $(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)$