A. Monke's Favourite Function
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Monke likes mind-boggling functions that even a genius like him can't solve. The function is the following —

  • $$$f(0, x) = x$$$
  • $$$f(k, x) = \sum_{\substack{y \& x = y}} f(k - 1, y)$$$, in other words, summation of $$$f(k - 1, y)$$$ for all $$$y$$$ that are submask of $$$x$$$, i.e. $$$(y \& x = y)$$$.

Monke tried to write a code that finds $$$f(k, x)$$$ $$$\bmod$$$ $$$10^9 + 7$$$. When he runs that code, his computer catches on fire, he loses his mind and comes to you. Now, to calm him down (and to also prove you're more of a genius than him), you have to write a code that can calculate $$$f(k, x)$$$ $$$modulo$$$ $$$10^9 + 7$$$, which doesn't burn Monke's computer.

Input

The first line of input contains $$$t(1 \leq t\leq 10^5)$$$ — the number of test cases.

Each test case contains two integers $$$k, x (1 \leq k, x \leq 3\cdot10^5)$$$.

Output

Print $$$f(k, x) \bmod 10^9+7$$$.

Example
Input
3
1 1
1952 1971
69420 42069
Output
1
537162777
817139390