E. Exotic Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An array $$$a = [a_1,a_2,\dots , a_n]$$$ of length $$$n$$$ is exotic if and only if these two conditions are satisfied.

  • All array entries are integers from $$$1$$$ to $$$m$$$.
  • $$$a_{a_x+y} = x+y$$$ for all integers $$$x$$$, $$$y$$$ such that $$$1 \le x, y, a_x + y \le n$$$.

You are given two integers $$$n$$$ and $$$m$$$. Count the number of exotic arrays $$$a$$$ of length $$$n$$$. Since the answer can be very large, print it modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each of the next $$$t$$$ lines contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 10^9$$$) — the length of the array and the maximum allowed value.

Output

For each test case, print a single integer — the number of exotic arrays $$$a$$$ modulo $$$10^9 + 7$$$.

Example
Input
6
1 5
2 2
2 1
3 5
5 7
998244353 1000000000
Output
5
2
0
31
283
724174902
Note

In the first test case, $$$n = 1$$$. Every array of length $$$1$$$ is exotic. The answer is $$$5$$$.

In the second test case, $$$n = 2$$$, $$$m = 2$$$. The exotic arrays are $$$[1, 2]$$$ and $$$[2, 2]$$$.

In the third test case, $$$n = 2$$$, $$$m = 1$$$. No exotic arrays exist.