You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

在一个 $1*N$ 的棋盘上放置 $K$ 枚棋子，任意两枚棋子不能相邻，有多少种摆放方法？答案对 1e9+7 取模。

Format

Input

多组数据。第一行一个正整数 $T$ ，表示数据组数。后面 $T$ 行，每行两个正整数 $N$ 和 $K$ 。

Output

$T$ 行，每行一个整数表示答案，答案对 1e9+7 取模。

Samples

5
5 2
5 0
6 5
897 288
67563 10983

6
1
0
607016625
267208082

Limitation

$1≤T≤10^6$

• 对于33%的数据，$1≤N≤20$
• 对于66%的数据，$1≤N≤1000$
• 对于100%的数据，$1≤N≤10^5,0≤K≤N$