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