Mex Partition#11808
Sign in

Mex Partition

5 seconds
1,024 megabytes
Very hard

Given three integers , , and , consider arrays of length and sets of intervals of size that satisfy the following conditions:

For k = 1, 2, \dots, R, count the number of different pairs that satisfy the condition:

\text{mex}(a[l_1, \dots, r_1]) = \text{mex}(a[l_2, \dots, r_2]) = \dots = \text{mex}(a[l_k, \dots, r_k]).

The of the array is defined as the smallest non-negative integer that does not appear in . For example, if a = [0, 1, 2, 4], then \text{mex}(a) = 3, since is the smallest non-negative integer that is not present in .

Since the answer may be large, you need to output it modulo .

Input

The first line contains the number of test cases (1 \le t \le 200).

The only line of each test case contains three integers , , and (2 \le n \le 400, 1 \le m \le 10^6, 1 \le R \le n).

It is guaranteed that the sum of across all test cases does not exceed .

Output

For each test case, output integers separated by spaces on a new line  — the number of pairs that satisfy the above condition for k = 1, 2, \dots, R.

Examples

Example 1

Loading
Loading

Note

In the first test case:

For k=1, can only be , and the array can be [0, 0], [0, 1], [1, 0], and . Thus, there are different pairs :

  • (,).

  • (,).

  • (,).

  • (,).

For k=2, can only be \{[1,1],[2,2]\}, and the array can be and . Thus, there are different pairs :

  • (,\{[1,1],[2,2]\}).

  • (,\{[1,1],[2,2]\}).

Scoring

  1. ( points): t=1, n+m \le 10, R=1;

  2. ( points): t=1, n+m \le 10, R=n;

  3. ( points): m = 1;

  4. ( points): m = 2;

  5. ( points): m \le 5;

  6. ( points): R = 1;

  7. ( points): \sum n \le 100;

  8. ( points): no additional constraints;