311174: CF1944F1. Counting Is Fun (Easy Version)

F1. Counting Is Fun (Easy Version)time limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. The only difference between the two versions is the constraint on $n$. You can make hacks only if both versions of the problem are solved.

An array $b$ of $m$ non-negative integers is said to be good if all the elements of $b$ can be made equal to $0$ using the following operation some (possibly, zero) times:

• Select two distinct indices $l$ and $r$ ($1 \leq l \color{red}{<} r \leq m$) and subtract $1$ from all $b_i$ such that $l \leq i \leq r$.

You are given two positive integers $n$, $k$ and a prime number $p$.

Over all $(k+1)^n$ arrays of length $n$ such that $0 \leq a_i \leq k$ for all $1 \leq i \leq n$, count the number of good arrays.

Since the number might be too large, you are only required to find it modulo $p$.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three positive integers $n$, $k$ and $p$ ($3 \leq n \leq 400$, $1 \leq k \leq n$, $10^8 < p < 10^9$) — the length of the array $a$, the upper bound on the elements of $a$ and modulus $p$.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $2 \cdot 10^5$, and $p$ is prime.

Output

For each test case, on a new line, output the number of good arrays modulo $p$.

ExampleInput

4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353

Output

4
7
10
456615865

Note

In the first test case, the $4$ good arrays $a$ are:

• $[0,0,0]$;
• $[0,1,1]$;
• $[1,1,0]$;
• $[1,1,1]$.

题目大意：
这是一个关于判断数组是否“好数组”的问题。一个长度为m的非负整数数组b被称为“好数组”，如果可以通过以下操作（可能零次）使得b的所有元素变为0：

- 选择两个不同的下标l和r（1 ≤ l < r ≤ m），并将所有满足l ≤ i ≤ r的bi减1。

给定两个正整数n、k和一个素数p，需要计算所有长度为n的数组a（其中0 ≤ ai ≤ k）中“好数组”的数量。由于数量可能非常大，只需要求出其模p的结果。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^3），表示测试用例的数量。
- 每个测试用例包含一行，有三个正整数n、k和p（3 ≤ n ≤ 400，1 ≤ k ≤ n，10^8 < p < 10^9），分别表示数组a的长度、数组元素的上下界和模数p。

输出：
- 对于每个测试用例，输出一行，表示“好数组”的数量模p的结果。

示例：
输入：
```
4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353
```
输出：
```
4
7
10
456615865
```题目大意： 这是一个关于判断数组是否“好数组”的问题。一个长度为m的非负整数数组b被称为“好数组”，如果可以通过以下操作（可能零次）使得b的所有元素变为0： - 选择两个不同的下标l和r（1 ≤ l < r ≤ m），并将所有满足l ≤ i ≤ r的bi减1。 给定两个正整数n、k和一个素数p，需要计算所有长度为n的数组a（其中0 ≤ ai ≤ k）中“好数组”的数量。由于数量可能非常大，只需要求出其模p的结果。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^3），表示测试用例的数量。 - 每个测试用例包含一行，有三个正整数n、k和p（3 ≤ n ≤ 400，1 ≤ k ≤ n，10^8 < p < 10^9），分别表示数组a的长度、数组元素的上下界和模数p。 输出： - 对于每个测试用例，输出一行，表示“好数组”的数量模p的结果。 示例： 输入： ``` 4 3 1 998244853 4 1 998244353 3 2 998244353 343 343 998244353 ``` 输出： ``` 4 7 10 456615865 ```