+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- زرافه به تازگی تعدادی از زبان های بیگانگان (موجودات فضایی!) را کشف کردەاست. هر یک از زبان ها دارای یک الفبا بوده و هر کدام از این الفباها دارای هزاران حرف هستند. در هر زبان نیز به صورت عجیبی همەی کلمات به یک اندازه هستند (تعداد حرف برابر دارند). بیگانگان دوست دارند که کلمات شان زیبا باشد؛ بدین معناکه برای $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