#P8973. Increasing Subsequences

Increasing Subsequences

题目描述

长度为 NN 的序列:

p(1),p(2),…,p(N)p(1),p(2),\ldots,p(N)

如果它恰好由整数 1,2,…,N1,2,\ldots,N 各出现一次组成,则称其为一个排列。

如果存在下标:

1≤i1<i2<⋯<ik≤N,1\le i_1<i_2<\cdots<i_k\le N,

并且:

p(i1)<p(i2)<⋯<p(ik),p(i_1)<p(i_2)<\cdots<p(i_k),

那么称该排列包含一个长度为 kk 的递增子序列。

若排列 pp 包含长度为 BB 的递增子序列,但不存在长度为 B+1B+1 的递增子序列,则称这个排列的**递增度(degree of increase)**为 BB。

给定 NN 和 BB,请计算递增度恰好为 BB 的 NN 元排列数量。

由于答案可能非常大,请输出答案对 1,000,000,0001,000,000,000 取模后的结果。

输入格式

第一行一个整数 TT,表示测试数据组数:

1≤T≤60.1\le T\le 60.

接下来 TT 行,每行两个整数:

N B,N\ B,

满足:

1≤N≤40,1\le N\le 40, 1≤B≤5.1\le B\le 5.

输出格式

对于每组测试数据,输出一行:递增度恰好为 BB 的 NN 元排列数量对

10000000001000000000

取模后的结果。

样例

1
3 2
4