该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

代码较短的一集

题目描述

定义一个数组是short数组，当且仅当所有长度为 3 的连续子数组的元素和为偶数。

现在需要求出，长度为n，且所有元素均为不超过k的正整数的short数组数量。

答案请对1e9+7取模。

输入格式

第一行为一个正整数T表示测试数据量

接下来T行,每行两个整数 n,k ( 3<=n<= 1e9, 3<=k<=1e9)

输出格式

包括T行,每行一个整数

样例

样例输入

2
3 5
4 3

样例输出

62
21