Horde Chess | codechef |starters 81

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.09RLPJ6.png

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 –gsowR65.png

Test case 22: You need 44 pawns and there are 44 ways of arranging them as shown below –RhZAZqk.png
QCRK9tk.png
jegJBmR.png
tppIedL.png

Test case 33: You need 66 pawns and there is only 11 way of arranging them as shown below –3FfUs1z.png

click on below image to get the solution:

Leave a Reply

Your email address will not be published. Required fields are marked *

यकीन नहीं मानोगे! ये 9 जगहें हैं UP में जो ताजमहल को भी फीका कर देंगी! मेरठ: इतिहास, धर्म और खूबसूरती का संगम! घूमने के लिए ये हैं बेहतरीन जगहें रोज आंवला खाने के 10 धांसू फायदे जो आपको कर देंगे हेल्दी और फिट! Anjali Arora to play Maa Sita: रामायण फिल्म में सीता का रोल निभाएंगी अंजली अरोड़ा, तैयारियों में लगी? Rinku Singh : रिंकू सिंह ने अपने दाहिने हाथ पर बने टैटू का खोला राज, सुनकर हो जायेंगे दंग Panchayat Season 3 Release Date: फुलेरा में मचा भूचाल! क्या अभिषेक इस बार हार जाएगा?