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

سال رو به اتمام است و شرکت کوئرا قصد دارد نمای ساختمان خود را چشم‌نواز کند. سایر شرکت‌ها هم که کوئرا الگوی آنهاست تصمیم مشابهی می‌گیرند. نمای هر ساختمان $n$ طبقه به عرض $m$ از $n\times m$ پنجره تشکیل شده یعنی نمای هر طبقه از $m$ پنجره متوالی به عرض ۱ تشکیل شده است.

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

توضیح تصویر

حال مدیر هر شرکت مایل است بداند چند رنگ‌آمیزی چشم‌نواز برای نمای شرکتش وجود دارد! از آنجا که ممکن است این عدد بزرگ باشد باقی‌مانده جواب بر $10^9 + 7$ را خروجی دهید.

ورودی

در خط اول $t$ نشان‌دهنده تعداد شرکت‌ها می‌آید. $$ 1 \leq t \leq 200 , 000$$ در $t$ خط بعد در هر کدام به ترتیب دو عدد $n_i$ و $m_i$ می‌آید که به ترتیب نشان دهند تعداد طبقات و عرض شرکت $i$ام است. $$ 1 \le n_i, m_i \le 500, 000$$

خروجی

در خط $i$ام از $t$ خط خروجی جواب مساله را خروجی دهید.

مثال

ورودی نمونه ۱

4
1 3
2 2
3 3
187563 196327

خروجی نمونه ۱

ارسال پاسخ برای این سؤال