Expectation of Rank

Problem Description

Let $p$ be a prime number and $\mathbb{F}_p$ be the finite field with order $p$. Suppose $A$ is a square matrix of order $n$ and each of its entry is a random variable that uniformly distributed on $\mathbb{F}_p$. Please calculate the expectation of the rank of $A$, i.e., $\mathbb{E}[\mathrm{rank}(A)]$. In mathematics, a finite field, also known as a Galois field, is a set that contains a finite number of elements. These elements follow the operations of multiplication, addition, subtraction, and division, all of which satisfy the basic rules of arithmetic. The most common examples of finite fields are given by the integers mod $p$ when $p$ is a prime number. When we say $\mathbb{F}_p$ is a finite field with order $p$, it means that $\mathbb{F}_p$ contains exactly $p$ distinct elements, with $p$ being a prime number. The elements of $\mathbb{F}_p$ are the integers $0, 1, 2, ..., p-1$, and the operations of the field are performed modulo $p$. For instance, if $p=5$, then $\mathbb{F}_5$ is the set $\{0, 1, 2, 3, 4\}$, and in this field, $2+3=0$ and $4 \times 4=1$.

Input

The first line of the input contains an integer $T$ ($1 \leq T \leq 50$), denoting the number of test cases. Each of the following $T$ lines contains two integers $n, p$ ($1 \leq n \leq 5000$, $2 \leq p \leq 10^9$), denoting the order of the square matrix $A$ and the prime number $p$. It's guaranteed that the sum of $n$ in all test cases will not exceed $5000$.

Output

For each test case, output the expectation of the rank of $A$. You should output the answers modulo $10^9+7$. That is, if the answer is $\frac{P}{Q}$, you should output $P\cdot Q^{-1}\bmod 10^9+7$, where $Q^{-1}$ denotes the multiplicative inverse of $Q$ modulo $10^9+7$. It can be proved that the answer can always be expressed in this form.

Sample Input

2
2 2
2 3

Sample Output

812500007
802469143

Hint

The rank of the matrix

in $\mathbb{F}_3$ is $1$.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（8）