P11284 「GFOI Round 2」Strings

给你两个正整数 $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$ 取模后的值。

#### 【样例解释】 对于第一组数据，长度 $\le 3$ 的好的序列有 $[1, 1, 1], [1, 1, 2], [2, 2, 1], [2, 2, 2]$。 #### 【数据范围】 **本题采用捆绑测试且开启子任务依赖。** | 子任务编号 | $n \le$ | $m \le$ | 子任务依赖 | 分值 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $10^{18}$ | $1$ | 无 | $1$ | | $2$ | $10$ | $4$ | 无 | $7$ | | $3$ | $10^5$ | $10^{18}$ | $2$ | $28$ | | $4$ | $10^{18}$ | $10^{18}$ | $1, 2, 3$ | $64$ | 对于所有数据，满足： - $1 \le T \le 10$； - $3 \le n \le 10^{18}$； - $1 \le m \le 10^{18}$。