على أرضية كبيرة إلى ما لا نهاية، تحتاج إلى رصف عدد لا نهائي من البلاطات.
كل بلاطة لها نمط من الخلايا المربعة بحجم $n \times n$. تحتوي كل خلية في البلاطة على شريط إضاءة LED مثبت على طول حافتيها السفلية واليسرى، بألوان مختلفة تشكل نمطاً ملوناً.
النمط الموجود على كل بلاطة متطابق تماماً. عند رصف البلاطات، سنضع عدداً لا نهائياً من البلاطات جنباً إلى جنب دون فواصل، مما يشكل نمطاً كبيراً إلى ما لا نهاية من أشرطة الإضاءة.
يتوفر $k$ من الألوان المختلفة، وتحتاج إلى اختيار الألوان المقابلة لإجمالي $2n^2$ من أشرطة الإضاءة على بلاطة واحدة، وبعد ذلك ستقوم البلاطات الأخرى بتكرار مخطط التلوين هذا تلقائياً. عند رصف البلاطات، سيتم وضع جميع البلاطات في نفس الاتجاه، مما يعني أنه يمكن اعتبارها إزاحة مباشرة لبلاطة واحدة ثم تجميعها معاً دون دوران.
أثناء سيرك على الأرضية، تريد معرفة عدد المخططات المختلفة جوهرياً لتلوين البلاطات. نظراً لأن الأرضية لا نهائية، وقد يواجه الشخص اتجاهات مختلفة (الشمال، الجنوب، الشرق، الغرب) عند ملاحظة البلاطات، يتم تعريف مخططين على أنهما متماثلان جوهرياً إذا وفقط إذا:
عند ملاحظة مستوى الأرضية اللانهائي الناتج عن المخططين، إذا وجدت سلسلة من الإزاحات أو الدورانات (باستثناء الانعكاسات) التي يمكن أن تجعل ألوان أشرطة الإضاءة في جميع المواضع على الأرضية متطابقة تماماً، فعندئذٍ يُعتبر هذان المخططان متماثلين جوهرياً.
الإدخال
توجد حالات اختبار متعددة في ملف إدخال واحد. يحتوي السطر الأول من الإدخال على عدد صحيح موجب واحد $T$ ($1 \le T \le 10$)، يشير إلى عدد حالات الاختبار.
لكل حالة اختبار:
- يحتوي السطر الأول على عددين صحيحين $n$ و $k$ ($1 \le n \le 10^9$، $1 \le k \le 10^9$)، يمثلان حجم النمط وعدد الألوان على التوالي.
الإخراج
لكل حالة اختبار، اطبع سطراً واحداً يحتوي على عدد صحيح واحد يمثل عدد المخططات المختلفة جوهرياً، باقي القسمة على $10^9 + 7$.
مثال
إدخال 1
3 1 2 2 2 114514 5201314
إخراج 1
3 31 377726028
ملاحظة
توضح الصورة التالية 19 مخطط بناء عندما يكون $n = k = 2$ (لتوضيح تأثير الرصف بشكل أفضل، تُظهر كل صورة 9 بلاطات مرتبة في نمط $3 \times 3$، مع توفر أضواء LED بلونين داكن وفاتح). من خلال تبديل اللونين الداكن والفاتح لأول 12 مخططاً، يمكن الحصول على 12 مخططاً آخر، مما ينتج عنه إجمالي 31 مخططاً.
