统计好数组（困难版）

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

长度为 $m$ 的非负整数数组 $b$ 称为“好数组”，当且仅当可以执行若干次（可以为零次）以下操作，使所有元素都变为 $0$：

• 选择两个不同的下标 $l,r$（$1\le l<r\le m$），将区间 $[l,r]$ 中的每个元素都减去 $1$。

给定正整数 $n,k$ 和质数 $p$。在所有满足 $0\le a_i\le k$ 的长度为 $n$ 的数组 $a$ 中，求好数组的数量，并对 $p$ 取模。

输入格式

第一行一个整数 $t$，表示测试用例数。

接下来 $t$ 行，每行三个整数 $n,k,p$。

输出格式

对每个测试用例输出一行，表示答案对 $p$ 取模的结果。

样例输入

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

样例输出

4
7
10
456615865

样例说明

第一个测试用例的四个好数组分别是 $[0,0,0]$、$[0,1,1]$、$[1,1,0]$、$[1,1,1]$。

数据范围

对所有数据：

• $1\le t\le 1000$；
• $3\le n\le 3000$；
• $1\le k\le n$；
• $10^8<p<10^9$，且 $p$ 是质数；
• 所有测试用例的 $n^2$ 之和不超过 $10^7$。

本题采用独立测试点计分。

每个测试点独立计分。子任务按顺序构成主链：后一个子任务包含前一个子任务允许的输入范围。