Counting Rectangles

0

0 votes
Maths, Modular arithmetic, Basics of Combinatorics
Problem

Param loves teasing people and he has started to tease Shubham recently with reasons known only to them. Param offers Shubham that he wont stop until he solves a question for him. Since Shubham is weak with Maths, help him solve this problem. 

The question is very simple. Param will give Shubham two numbers K and P. Consider a 2-D Coordinate system with X- axis extending from [-K,K]  and Y axis also from [-K,K]. Param asks Shubham to count the number of rectangles that can be formed in this coordinate system with all 4 corners lying on integral coordinates.

Integral coordinates refer to all points (x,y) such that both x and y are integers and lie in the range [-K,K]. 

Since answer could be very very large , print (4*ans)%P. It is guaranteed that P is a prime number. (Do not forget to multiply your answer by 4 and then take modulo).

NOTE:-You are not allowed to use JAVA/PYTHON/PYTHON3 for this question

**INPUT** :

The Input contains  an integer T and P denoting number of test Cases and the prime number P . T lines follow. Each line contains an integer K.

**OUTPUT** :

For each test case, you have to print (4*ans)%P in a newline.

**CONSTRAINTS** :

1<=T<=100000

1<=K<=10^7

2<=P<=10^9    (30 Points)

2<=P<=10^16  (70 Points)

 

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Since K=1, and P=5, X axis extends from [-1,1] and Y axis also extends from [-1,1]. We can generate 

4 Rectangles of 1*1

2 Rectangles of 1*2

2 Rectangles of 2*1

1 Rectangle of 2*2

Hence total 9 Rectangles. So, output is (4*9)%P = 36%5 = 1.

Editor Image

?