Xét thuật toán bubble sort (nguồn Wikipedia):

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        /* do this at most K times */
        swapped := false
        for i := 1 to n-1 inclusive do                     
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped
end procedure

Một hoán vị độ dài ~n~ được gọi là hoán vị đẹp nếu dãy con tăng dài nhất (LIS) của hoán vị đó đạt ít nhất ~n-1~.

Đếm số hoán vị có thể trở thành hoán vị đẹp sau ~k~ lần vòng lặp trong của thuật toán bubble sort được thực hiện (theo module đã cho).

Input

Dòng đầu tiên chứa số nguyên dương ~T (T \leq 50)~ là số bộ dữ liệu của test.

Mỗi dòng trong ~T~ dòng tiếp theo chứa ba số nguyên dương ~n, k, mod (n, k \leq 50, mod \leq 10^{9} + 7)~.

Output

In ra ~T~ dòng mỗi dòng gồm một số nguyên duy nhất là kết quả của bộ dữ liệu tương ứng.

Sample Input 1

2
6 3 998244353
8 3 998244353

Sample Output 1

696
22872