Predict The Frequency

Luis was sleeping. He suddenly woke up with three positive integers $N$, $M$ and $X$. He told his younger brother Hansi these three integers. Hansi is too young and weird. He wrote all possible distinct arrays of length $N$ such that only integers from $1$ to $M$ occurs in it and none of their frequency is more than $X$. Note that, any element in an array will be in $[1, M]$, but not all integers from $[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 $P$.

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

Input

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

Each of the next $T$ lines will have three space-separated integers $N$, $M$ and $X$ $(1 \le N, M ,X \le 200)$ describing the testcase.

Output

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

Sample

3
998244353
2 2 1
2 2 2
2 1 1

2
6
0

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

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

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