Подвійне намисто#3207
Стен-кролик знову забув про свою річницю весілля. Як йому привітати Франсін? Можливо, ще є шанс знайти те намисто, яке було загублене дуже давно. Воно було красивим, блискучим, випромінювало щастя. Воно виглядало як звичайне намисто з намистин однакового розміру, але різних кольорів. Однак у ТОГО намиста була унікальна особливість — воно складалося з двох рядів намистин замість одного. Для наочності можна пронумерувати намистини у намисті довжини так:
1 3 5 7 9
0 2 4 6 8
У цьому намисті сусідні намистини такі: 0 і 1, 1 і 3, 2 і 4, 9 і 1 тощо. Кожна намистина має рівно три сусідні. На жаль, знайти оригінальне намисто вже неможливо, але Стен може спробувати зробити таке ж, як було у Франсін. Стен пам’ятає лише три речі: довжину намиста, кількість різних кольорів, використаних для виготовлення намиста, і те, що жодні дві сусідні намистини не були одного кольору. Знайдіть кількість можливих намист (два намиста вважаються різними, якщо хоч би на одній позиції відрізняється колір намистини). Нумерація намистин фіксована, оскільки намистини 0 та 1 завжди знаходяться біля застібки. Шанси, що Стен зробить саме ТЕ намисто, дуже малі, адже можливостей багато. Тому виведіть відповідь по модулю 10^9+7 (1000000007).
Перший рядок містить одне ціле число (1 \leq T \leq 50000) — кількість тестів. Далі йдуть рядків, у кожному з яких два цілих числа: та , де (2 \leq n \leq 10^{18}) — довжина намиста, а (1 \leq c \leq 10^9) — кількість різних кольорів, доступних на фабриці.
Для кожного тесту виведіть одне число у окремому рядку — відповідь на задачу.
Приклад 1