+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Saman loves brackets (or parentheses). He calls a sequence of ‘(’ and ‘)’ characters a “valid bracket sequence” if either: + It’s an empty sequence, or + For each open bracket, we can find a closed bracket on its right such that the substring between these two brackets forms a valid bracket sequence, and such that after removing that substring, the remaining brackets also form a valid bracket sequence. For example, `(())` and `()()` are both valid, while `)(` and `())(()` are not. Furthermore, he calls a string of parentheses “$k$-valid” if, f, after adding $k$ open brackets to its left and $k$ closed brackets to its right, it is valid (either because it was valid before, or because it became valid). For example `)(` and `())(()` are both $1$-valid, while `))((` is 2-valid. Saman is curious to find for any given $n$ and $k$ how many bracket sequences there are with length $2n$ that are $k$-valid. Because the result may be very large, Saman is only interested in its remainder after dividing it by $10^9 + 7$. Help Saman by writing a program that quickly calculates this number for $Q$ different queries. # input The first line contains one integer $Q$, the number of queries Saman is interested in. The next $Q$ lines contain each a pair of integers $n_i$ and $k_i$. $$1 \leq n \leq 10^5$$ $$1 \leq n_i, k_i \leq 10^6$$ # output You need to write $Q$ lines containing each the result of the $i$-th query: for each query, print the number of strings of length $2n_i$ that are $k_i$-valid, modulo $10^9 + 7$ # example ### sample input 1 ``` 3 2 1 4 2 5 3 ``` ### sample output 1 ``` 5 62 242 ```