评委们坐在一起，想要品尝 Khoshaf（一种浸泡在杏汁中的干果混合物）。他们去了一家餐馆点餐，却发现只剩下一份了，于是他们决定出一道题，第一个解决它的人将获得这份剩下的餐点。

题目如下：给定四个整数 $N, K, L$ 和 $R$，计算长度为 $N$ 且包含范围 $[L, R]$ 内（包含边界）整数的数组个数，要求这些数组恰好有 $K$ 个和能被 $3$ 整除的连续子区间。输出答案对 $10^9 + 7$ 取模的结果。请注意，子区间可以重叠。你能帮主评委得到最后这份餐点吗？

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例包含一行，包含四个整数 $N, K, L$ 和 $R$ ($1 \le N, K \le 10^4, 1 \le L \le R \le 10^9$)，如题目描述中所述。

输出格式

对于每个测试用例，打印一行，包含长度为 $N$ 且包含范围 $[L, R]$ 内（包含边界）整数，且恰好有 $K$ 个和能被 $3$ 整除的连续子区间的数组个数。输出答案对 $10^9 + 7$ 取模。

样例

输入 1

3
3 2 1 3
4 3 1 3
5 4 4 8

输出 1

6
20
1808

说明

在第一个测试用例中，以下任何数组都将恰好包含两个和能被 $3$ 整除的子区间：

$[1,2,1] \to$ 子区间为 $[1,2]$ 和 $[2,1]$，索引分别为 $[0,1]$ 和 $[1,2]$。 $[1,3,2] \to [3], [1,3,2]$ $[2,1,2] \to [2,1], [1,2]$ $[2,3,1] \to [3], [2,3,1]$ $[3,1,3] \to [3], [3]$ $[3,2,3] \to [3], [3]$