Problem Description
In certain areas of the world, there are triangular fishies. Rar the Cat has recently caught a triangular fish of size N and he has noticed that he has numbers on it.
A triangle fish of size N has N rows of numbers. The ith row has i numbers, numbered ascendingly from 1 to i.
For example, a fish of size 5 has the following numbers:
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
Rar the Cat wants to know the sum of all the numbers on the triangular fish. However, as this number can be very big, he wants to know the remainder when that sum is divided by M. (Sum mod M)
Input
The input will contain 2 integers, N followed by M, on a single line.
Output
Print the sum of the numbers on the triangular fish with size N
Limits
0 < M ≤ 5000000
Subtasks
Subtask 1 (23 marks): 0 < N ≤ 5000
Subtask 2 (32 marks): 0 < N ≤ 5000000
Subtask 3 (45 marks): 0 < N ≤ 2000000000
Subtask 4 (0 marks): Sample Testcases
Sample Input 1
5 100
Sample Output 1
35
Sample Input 2
5 7
Sample Output 2
0
Sample Input 3
5 10
Sample Output 3
5