CF403D Beautiful Pairs of Numbers

The sequence of integer pairs $ (a_{1},b_{1}),(a_{2},b_{2}),...,(a_{k},b_{k}) $ is beautiful, if the following statements are fulfilled: - $ 1

The first line contains integer $ t $ ( $ 1

For each test from the input print the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ . Print the answers to the tests in the order in which the tests are given in the input.

In the first test sample there is exactly one beautiful sequence: $ (1,1) $ . In the second test sample, the following sequences are beautiful: - $ (1,1) $ ; - $ (1,2) $ ; - $ (2,2) $ . In the fourth test sample, the following sequences are beautiful: - $ (1,1) $ ; - $ (1,2) $ ; - $ (1,3) $ ; - $ (2,2) $ ; - $ (2,3) $ ; - $ (3,3) $ . In the fifth test sample, the following sequences are beautiful: - $ (1,1),(2,3) $ ; - $ (1,2),(3,3) $ . In the third and sixth samples, there are no beautiful sequences.