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