Problem
Imagine you have a �×�N×N chessboard.
- The horizontal rows are called ranks and are numbered from 11 to �N from bottom to top.
- The vertical columns are called files and are numbered from 11 to �N from left to right.
- A square in the ��ℎith rank and ��ℎjth file is represented as (�,�)(i,j).
A chess pawn present in the square (�,�)(i,j) can attack on the squares (�+1,�−1)(i+1,j−1) and (�+1,�+1)(i+1,j+1) if they exist.
For simplicity, assume that pawns do not promote on the last rank (although they do in real chess). Note that no pawn can attack any square on the first rank.
A single pawn might be very weak but a horde of pawns can be very strong (for example, in Horde Chess).
To prove this point, you want to place minimum number of pawns in such a way that they attack every square on the board except the squares on the first rank.
Your task is to calculate two things:
- The minimum number of pawns you need;
- The number of ways you can arrange those pawns to achieve this goal. Since the number of ways can be very large, calculate it modulo 109+7109+7.
Input Format
- The first line of input contains a single integer �T, the number of test cases.
- Each test case consists of a single line of input containing a single integer �N, the number of ranks and files in the chessboard.
Output Format
For each test case, print a single line, containing two integers, the minimum number of pawns needed and the number of ways of arranging them modulo 109+7109+7.
Note that the modulo is to be taken only for the number of ways of arranging the pawns and not the minimum number of pawns.
Constraints
- 1≤�≤1051≤T≤105
- 2≤�≤1092≤N≤109
Sample 1:
Input
Output
5 2 3 4 5 11
2 1 4 4 6 1 12 1 60 1048576
Explanation:
Test case 11: You need 22 pawns and there is only 11 way of arranging them, as shown below –
Test case 22: You need 44 pawns and there are 44 ways of arranging them as shown below –
Test case 33: You need 66 pawns and there is only 11 way of arranging them as shown below –
