İkiqat boyunbağı#3207
Stan dovşanı yenə toy ildönümünü unudub. Bəs o, Fransini necə təbrik edə bilər? Bəlkə hələ də çoxdan itmiş həmin boyunbağını tapmaq şansı var. O, gözəl, parlaq, xoşbəxtlik saçırdı. Sadə boyunbağıya bənzəyirdi: eyni ölçülü, lakin müxtəlif rəngli muncuqlardan ibarət idi. Amma MƏHZ O boyunbağının fərqli cəhəti onda idi ki, bir yox, iki sıra muncuqdan ibarət idi. Aydınlıq üçün, uzunluğu olan boyunbağının muncuqlarını aşağıdakı kimi nömrələyə bilərik:
1 3 5 7 9
0 2 4 6 8
Bu boyunbağında bitişik muncuqlar bunlardır: 0 və 1, 1 və 3, 2 və 4, 9 və 1 və s. Hər bir muncuğun məhz üç bitişik muncuğu var. Təəssüf ki, artıq orijinal boyunbağını tapmaq mümkün deyil, amma Stan ona bənzər birini düzəltməyə cəhd edə bilər. Stan yalnız üç şeyi xatırlayır: boyunbağının uzunluğunu, boyunbağının hazırlanmasında istifadə olunan müxtəlif rənglərin sayını və heç iki bitişik muncuğun eyni rəngdə olmadığını. Mümkün boyunbağıların sayını tapın (iki boyunbağı yalnız ən azı bir muncuq eyni mövqedə fərqli rəngdə olduqda fərqli sayılır). Muncuqların nömrələnməsi sabitdir, çünki 0 və 1 nömrəli muncuqlar həmişə bağlama yaxınlığındadır. Stanın MƏHZ O boyunbağını düzəltmək ehtimalı çox azdır, çünki müxtəlif seçimlər çoxdur. Ona görə də, cavabı 10^9+7 (1000000007) modulu üzrə çıxış edin.
Birinci sətirdə tək tam ədəd (1 \leq T \leq 50000) — testlərin sayı verilir. Sonra isə hər biri iki boşluqla ayrılmış tam ədəddən ibarət sətir gəlir: və , burada (2 \leq n \leq 10^{18}) — boyunbağının uzunluğu, (1 \leq c \leq 10^9) — fabrikdə mövcud olan müxtəlif rənglərin sayıdır.
Hər bir test üçün cavabı ayrıca sətirdə çap edin.
Nümunə 1