Limits 2s, 256 MB

Luis was sleeping. He suddenly woke up with three positive integers NN, MM and XX. He told his younger brother Hansi these three integers. Hansi is too young and weird. He wrote all possible distinct arrays of length NN such that only integers from 11 to MM occurs in it and none of their frequency is more than XX. Note that, any element in an array will be in [1,M][1, M], but not all integers from [1,M][1, M] may be present in an array.

Luis defines score of an array as the maximum frequency of its elements in it. Can you tell the sum of score of all arrays that Hansi wrote? Print it modulo PP.

Frequency of an element in an array is defined as the number of times the element occurs in that array.


First line of the input will have two space-separated integers TT (1T105)(1 \le T \le 10^5), number of testcases and integer PP(108P109)(10^8 \le P \le 10^9). PP will be prime.

Each of the next TT lines will have three space-separated integers NN, MM and XX (1N,M,X200)(1 \le N, M ,X \le 200) describing the testcase.


For each testcase, output an integer ansans (0ans<P)(0 \le ans \lt P), which is the sum of score of all arrays that Hansi wrote, modulo PP.


2 2 1
2 2 2
2 1 1

In first test, Hansi will write [1,2][1, 2] and [2,1][2, 1]. Score of both arrays is 11. So, the output will be 1+1=21+1=2.

In second test, Hansi will write [1,1][1, 1], [1,2][1, 2], [2,1][2, 1] and [2,2][2, 2]. Score of the arrays are 22, 11, 11, 22 respectively. So, the sum will be 66.

In third test, Hansi will not be able to write any array. So, the output will be 00.


Login to submit.


0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.