T3 快速排序机

题目信息

时间限制: 1s

空间限制: 256M

输入文件: c.in

输出文件: c.out

题目描述

C 酱发明了快速排序机，快速排序机的核心代码如下：

int a[MAXN];
int partition(int l, int r) { //这部分和快排相同
    int x = a[r];
    int i = l;
    for (int j = l; j < r; j++) {
        if (a[j] < x) {
            swap(a[i], a[j]);
            ++i;
        }
    }
    swap(a[i], a[r]);
    return i;
}

void Qsort(int l, int r, int h) {
    if(l < r && h > 1) {
        int m = partition(l,r);
        Qsort(l, m - 1, h - 1);
        Qsort(m + 1, r, h - 1);
    }
}

不难看出，C 酱快速排序机的核心代码和普通的快速排序代码的主要差异是，快速排序机的核心代码增加了递归栈的深度限制，毕竟以 C 酱目前的硬件知识水平，她不得不通过对递归栈的深度限制来避免快速排序机的栈溢出问题。

那么对于给定的正整数 $n, k$，有多少个 $1, 2, \dots, n$ 的排列 $a[1\dots n]$ 在调用 Qsort(1, n, k) 后能完成排序呢？

输入格式

输入包含多组测试数据。

第一行包含两个整数 $T, q$，依次表示测试数据的数量和一个用于输出的模数。

接下来 $T$ 行，每行描述一组测试数据，包含两个正整数 $n, k$，依次表示排列的长度以及递归的最大深度。

输出格式

对于每组测试数据，输出一行一个整数表示这组测试数据的答案对 $q$ 取模的值。

样例

样例输入 1

4 998244353
4 1
4 2
4 3
4 4

样例输出 1

1
8
20
24

样例输入 2

5 10007
10 4
40 3
30 2
20 10
300 20

样例输出 2

6401
2733
5369
3539
8445

数据范围与提示

• 对于测试点 1-2，$n, k \leq 5$
• 对于测试点 3，$n \leq 50, k=1$
• 对于测试点 4，$n \leq 50, k=2$
• 对于测试点 5-6，$n \leq 13$
• 对于测试点 7-10，$n, k \leq 300$
• 对于 $100\%$ 的数据，$T \leq 500,1 \leq n, k \leq 300,10^8 \leq q \leq 10^9$