题目描述

对于一个字符串 $S$，定义它的后缀自动机 $\mathcal{S}(S)$ 为一个接受 $S$ 的所有后缀的最小确定有限自动机（DFA）。具体定义如下：

• $\mathcal{S}(S)$ 是一张有向无环图。图中的结点称为状态，有向边称为状态之间的转移。
• 图中存在一个源点 $t_0$，称为初始状态。从 $t_0$ 出发可以到达其他所有状态。
• 每条转移都标有一个字母。从同一个状态出发的所有转移所标记的字母两两不同。
• 图中存在一个或多个终止状态。从初始状态 $t_0$ 出发，如果最终到达一个终止状态，那么路径上所有转移的字母依次连接起来，一定构成字符串 $S$ 的一个后缀；同时，$S$ 的每个后缀都能够由一条从 $t_0$ 到某个终止状态的路径构成。
• 在所有满足上述条件的自动机中，$\mathcal{S}(S)$ 的状态数最少。

定义 $f(S)$ 为字符串 $S$ 对应的后缀自动机的状态数。例如：

$$f(\texttt{aa})=3,\qquad f(\texttt{ab})=3,\qquad f(\texttt{aab})=4,\qquad f(\texttt{abb})=5.$$

现在，对于所有长度为 $n$、字符集为

$$\Sigma=\{1,2,\ldots,k\}$$

的字符串 $S$，求所有 $f(S)$ 的总和。

由于答案可能很大，你只需要输出答案对给定整数 $P$ 取模后的结果。

输入格式

输入包含多组测试数据。

第一行包含两个正整数 $T,P$，分别表示测试数据组数和模数。所有测试数据使用相同的模数 $P$。

接下来 $T$ 行，每行包含两个整数 $n,k$，表示字符串长度和字符集大小。

输出格式

对于每组测试数据，输出一行一个整数，表示答案对 $P$ 取模后的结果。

样例

3 1000000007
2 2
3 2
3 3

12
34
114

数据范围

对于 $100\%$ 的数据：

• $1\le T\le 10^5$；
• $1\le k\le n\le 40$；
• $10^8\le P\le 10^9+9$；
• 不保证 $P$ 为质数。

各子任务的限制如下：

子任务	分值	额外限制
$1$	$5$	$n\le 8$
$2$	$15$	$k=2$
$3$	$10$	$n\le 16$
$4$		$n\le 24$
$5$		$n\le 28$
$6$		$n\le 32$
$7$		$n\le 34$
$8$		$n\le 36$
$9$		$n\le 38$
$10$		$n\le 40$