Как же надоели задачки про ожерелья, одно и то же из года в год. И сегодня опять такая же задачка. Правильный подход к решению таких задач примерно такой: - \textit{Что там?} - \textit{Ожерелья}. - \textit{Откладывай на "потом"}... Ну как же так? Ну почему нельзя было назвать задачку как-нибудь по другому? Браслет, хотя бы... Вот и придётся опять решать. Итак, крилик Стэн опять забыл про годовщину... На этот раз всё так же серьёзно, как и в прошлый, вобщем осталось недолго. Возможно ещё есть шанс найти то одно ожерелье, которое было так давно потеряно. Ожерелье было прекрасным... оно сияло, излучало счастье... Выглядело оно как обычное ожерелье из разноцветных бусинок, всех одинакового размера. Отличительной чертой можно выделить то, что ожерелье состояло из двух рядов бусинок, вместо одного. Для большей наглядности пронумеруем бусинки в ожерелье длиной \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 Для каждого теста вывести одно число в отдельной строке -- ответ на задачу.