על רצפה אינסופית בגודלה, עליכם לרצף מספר אינסופי של אריחים.
לכל אריח יש תבנית של תאים ריבועיים בגודל $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 סכימות.
