题目描述

奇安凡尼银行建于城市主干道右侧的显眼位置，其规模为全公国之最，数家葡萄园借助它的投资而建成。

你决定去银行取钱。然而，由于人数众多、手续繁杂，你的业务迟迟没有得到办理。为了消遣，你和旁边一同等待的客户玩起了卡牌游戏。

由于你们都厌倦了传统的 Gwent 玩法，于是决定设计一种移牌游戏。

最初有 $n$ 个牌堆围成一个环，依次编号为 $1\sim n$，每个牌堆中都有 $m$ 张牌。接下来，你们一共进行恰好 $m$ 次操作。

每次操作中，你需要选择一个编号 $i$，从第 $i$ 个牌堆中取出一张牌，并将其放入相邻的一个牌堆中：

• 放入左侧牌堆，编号为 $(i+n-2)\bmod n+1$；
• 或放入右侧牌堆，编号为 $i\bmod n+1$。

也就是说，第 $i$ 个牌堆的牌数减少 $1$，所选择的相邻牌堆的牌数增加 $1$。

正当你们准备进一步约定时，一旁的观众小声问道：“这场牌可能出现多少种结果呢？”你的对手头脑异于常人，在一秒内就报出了结果数对 $998244353$ 取模的答案。你不甘示弱，于是决定报出结果数对 $10^9+7$ 取模的答案。

两种结果不同，当且仅当至少存在一个编号的牌堆，在两种结果中的牌数不同。

请计算经过恰好 $m$ 次操作后，可能得到多少种不同的牌堆数量配置。

输入格式

第一行包含一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行包含两个整数 $n,m$，含义如题目描述所示。

输出格式

对于每组数据，输出一行一个整数，表示不同结果的数量对 $10^9+7$ 取模后的值。

样例

3
4 1
4 5
8 10

8
216
573661

数据范围与约定

• 对于 $20\%$ 的数据，$n,m\le 5$；
• 对于 $40\%$ 的数据，$n,m\le 100$；
• 对于另外 $20\%$ 的数据，$n,m$ 均为偶数；
• 对于另外 $10\%$ 的数据，$m$ 为偶数；
• 对于全部数据，$1\le T\le 5$，$1\le n\le 5000$，$0\le m\le 5000$。