Chess

你现在有一个棋盘，上面有 $n$ 个格子，格子从左往右，$1,\ldots,n$ 进行标号。你可以在棋盘上放置恰好 $m$ 个传送器，并且对于每个传送器设置传送位置。

传送位置需满足：对于在 $i$ 号格子上的传送器，传送目标位置 $j$ 满足 $j < i$。
$1$ 号格子不能放置传送器。

现在有一名玩家，拿着一枚 $1,\ldots,11$ 的骰子（骰子每次等概率地投出 $1$ 到 $11$ 中的一个数字），从位置 $1$ 开始，用骰子决定前进步数，即如果当前在位置 $y$ 且投出数字 $x$，那棋子将会跳到位置 $y+x$。如果棋子跳到棋盘外的位置（$x+y>n$），玩家失败。如果位置 $y+x$上恰好有个传送器，那玩家的棋子立刻会被传送到传送器目标位置。如果传送器目标位置有另一个传送器，玩家的棋子会沿着另一个传送器继续传送。这个过程持续若干次，直到目标位置没有传送器为止。

如果玩家棋子可以到达点 $n$ 且不被传送到别的地方（意味着位置 $n$ 没有传送器），则玩家获胜。

问现在有多少种不同的放置传送器的方法，使得玩家有可能获胜。如果摆放传送器的格子不同或者某个格子上的传送器传送的位置不同则视为不同的方案。

每个格子最多放置一个传送器。

第一行一个正整数 $test~(1 \leq test \leq 20)$ 表示数据组数。

对于每组数据，第一行两个整数 $n, m~(1 \leq n \leq 1000, 0 \leq m \leq 1000)$ 表示格点数和传送器数。

对于每组数据，一行一个整数表示答案模 $10^9+7$。如果无解（没有任何获胜的方案），输出 $-1$。

1
12 10

3628800

2020 年百度之星·程序设计大赛 - 初赛三