The longest common subsequence (LCS) problem is to find the longest subsequence common to two given sequences. (Note that a subsequence is different from a substring, for the terms of the former need not be consecutive terms of the original sequence.)

Here the first sequence is infinite ie. length is not defined.

This sequence is

0,N,2N,3N,4*N .........

for a given prime N.

Second sequence is defined as follows. It is of length K.

This sequence is C(K,1), C(K,2), C(K,3), C(K,4), ....... .... C(K,K).

C(n,k) is define as

You have the ability to arrange this sequence in any order you want to.

Print the longest common subsequence of two sequences, where second sequence can be modified in any order.

Input:

First line contains T, the number of testcases. Each testcase consists of two space seperated integers denoting K and N.

Output:

For each testcase, print the required answer modulo 10^9 + 7.

Constraints:

1 <= T <= 1000

1 <= K <= 10^18

1 <= N <= 10^9

N is prime.