题目描述

长度为 $N$ 的序列：

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

如果存在下标：

并且：

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

若排列 $p$ 包含长度为 $B$ 的递增子序列，但不存在长度为 $B+1$ 的递增子序列，则称这个排列的**递增度（degree of increase）**为 $B$。

给定 $N$ 和 $B$，请计算递增度恰好为 $B$ 的 $N$ 元排列数量。

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

输入格式

第一行一个整数 $T$，表示测试数据组数：

接下来 $T$ 行，每行两个整数：

满足：

输出格式

对于每组测试数据，输出一行：递增度恰好为 $B$ 的 $N$ 元排列数量对

取模后的结果。

样例

1
3 2

4