+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بالأخره پس از دردسرهای فراوان لبو و یار به هم رسیدند! حال مراسم ازدواج آن‌هاست! در این مراسم فردی از خانواده‌ی لبو در مقابل فردی از خانواده‌ی یار ایستاده و بازی دونفره و نوبتی زیر را باهم انجام می‌دهند: در این بازی $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)$$