SP598 INCR - Increasing Subsequences

一个由数字 1 到 N 组成的序列 **p(1)**, **p(2)**, ..., **p(N)** 被称为排列，当且仅当序列中的所有元素互不相同。 如果一个排列 **p** 中存在序号满足 1 ≤ $i_1$ < $i_2$ < ... < $i_k$ ≤ N，使得对应的元素 **p($i_1$)** < **p($i_2$)** < ... < **p($i_k$)**，那么这个子序列就是一个递增子序列，长度为 **k**。 当一个排列的最长递增子序列长度为 **B**，而不存在长度为 **B+1** 的递增子序列时，称该排列的递增度为 **B**。 你的任务是编写一个程序，给定整数 **N**，计算具有递增度 **B** 的排列数量。由于结果可能非常大，需要对 1 000 000 000 取模。

第一行包含一个整数 **T**（1 ≤ **T** ≤ 60），表示测试用例的数量。接下来有 **T** 行描述每个测试用例。 每个测试用例包含两个整数 **N** 和 **B**（1 ≤ **N** ≤ 40, 1 ≤ **B** ≤ 5），用一个或多个空格分隔。

对于每个测试用例，输出一行，表示具有递增度 **B** 的排列数量对 1 000 000 000 取模后的结果。 **本翻译由 AI 自动生成**