T289919 [DMOI-R1] 农场

小 A 是一个农场主，有着许许多多的农场，但是他并不是非常聪明……

小 A 现在有 $x$ 个 $k$ 边形的农场，每个农场的顶点的点权可以为 $1$ 到 $k$ 之间的一个整数。但是小 A 有一个强迫症，他希望**存在**农场的点权和**不为** $\sum\limits_{i=1}^ki$，即合法条件。可惜他是一个死脑筋，需要你来帮帮他。 给定 $k$，有 $T$ 个询问，每一次询问给出 $x$，求共有多少种合法情况，答案对 $p$ 取模。

无

无

#### 样例1解释 可生成 $x=4$，即有 $4$ 个五边形农场，每个农场都有 $5$ 个点，即总共有 $20$ 个点，每个点都有 $5$ 个点权取值方案，即如果没有限制的话就有 $5^{20}$ 种权值方案，而加上限制后的权值方案数模上 $p=871168342$ 可得 $469566172$。 #### 数据范围： 对于 $10\%$ 的数据，$T=1$，$L\ ,k\le5$。 对于 $50\%$ 的数据，$T\leq 10^5$。 对于 $100\%$ 的数据，$1 \leq T\leq10^7$，$3\leq k\leq 9$，$2\leq p\leq 10^9$，$1\leq x\leq L\leq 10^{18}$，$0\leq seed