Time limit: 0.05s
Memory limit: 128MB
Input:
Task
Consider a circle. On the circle, arbitrary points are designated. If lines are drawn between all pairs of points, what is the maximum number of pieces into which the circle can be decomposed? Answer such scenarios.
Input data
The program reads the number from standard input and on each of the next lines reads a number , representing the number of points in the respective scenario.
Output data
On the next lines, the program will print the answers for each scenario to standard output, modulo .
Restrictions and specifications
- It is recommended to use fastio.
- For 25 points, , .
- For another 50 points, , .
- Since the answer can be very large, it will be displayed modulo .
Example
stdin
6
1
2
3
4
5
6
stdout
1
2
4
8
16
31
Explanation
For the fourth scenario, one of the possible optimal arrangements of the points is as follows:
