It's been a long summer's day, with the constant chirping of cicadas and the heat which never seemed to end. Finally, it has drawn to a close. The showdown has passed, the gates are open, and only a gentle breeze is left behind. Your predecessors had taken their final bow; it's your turn to take the stage. Sorting through some notes that were left behind, you found a curious statement named Problem 101 : Given a positive integer sequence (a_1,a_2,\ldots,a_n), you can operate on it any number of times. In an operation, you choose three consecutive elements (a_i,a_{i+1},a_{i+2}), and merge them into one element (\max(a_i+1,a_{i+1},a_{i+2}+1)). Please calculate the maximum number of operations you can do without creating an element greater than (m). After some thought, you decided to propose the following problem, named Counting 101 : Given (n) and (m). For each (k=0,1,\ldots,\left\lfloor\frac{n-1}{2}\right\rfloor), please find the number of integer sequences (a_1,a_2,\ldots,a_n) with elements in (1, m), such that when used as input for Problem 101 , the answer is (k). As the answer can be very large, please print it modulo (10^9+7). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1\le t\le10^3)). The description of the test cases follows. The only line of each test case contains two integers (n), (m) ((1\le n\le 130), (1\le m\le 30)). For each test case, output (\left\lfloor\frac{n+1}{2}\right\rfloor) numbers. The (i)-th number is the number of valid sequences such that when used as input for Problem 101 , the answer is (i-1), modulo (10^9+7). In the first test case, there are (2^3=8) candidate sequences. Among them, you can operate on (1,2,1) and (1,1,1) once; you cannot operate on the other (6) sequences.