题目背景

English statement. You must submit your code at the Chinese version of the statement.

题目描述

给你两个正整数 $n, m$。

我们称一个长度为 $k$ 的正整数序列 $a_1, a_2, \ldots, a_k$ 是好的当且仅当：

• $\forall i \in [1, k], 1 \le a_i \le m$；
• 存在一个正整数 $l \in [1, \frac{k}{3}]$ 满足：$\forall i \in [1, l], a_i = a_{2l + 1 - i}$。

求有多少个长度 $\le n$ 的好的序列，对 $10^9 + 7$ 取模。

输入格式

本题有多组测试数据。

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

对于每组测试数据：

第一行包含两个正整数 $n, m$。

输出格式

对于每组数据，输出一行一个非负整数，表示答案对 $10^9 + 7$ 取模后的值。

4
3 2
5 3
10 4
100000 998244353123456

4
117
430352
967771719

提示

【样例解释】

对于第一组数据，长度 $\le 3$ 的好的序列有 $[1, 1, 1], [1, 1, 2], [2, 2, 1], [2, 2, 2]$。

【数据范围】

本题采用捆绑测试且开启子任务依赖。

对于所有数据，满足：

• $1 \le T \le 10$；
• $3 \le n \le 10^{18}$；
• $1 \le m \le 10^{18}$。