T533519 「GFOI Round 2」Strings (English ver.)

**[Chinese statement](https://www.luogu.com.cn/problem/P11284). You must submit your code at the Chinese version of the statement.**

Given two positive integers $n$ and $m$. We define a sequence of positive integers $a_1, a_2, \ldots, a_k$ of length $k$ as "good" if and only if: - $\forall i \in [1, k], 1 \leq a_i \leq m$; - There exists a positive integer $l \in [1, \frac{k}{3}]$ such that: $\forall i \in [1, l], a_i = a_{2l + 1 - i}$. You need to determine how many good sequences of length $\leq n$ exist, modulo $10^9 + 7$.

无

无

#### Sample Explanation For the first test case, the good sequences of length $\le 3$ are $[1, 1, 1], [1, 1, 2], [2, 2, 1], [2, 2, 2]$. #### Subtasks and Constraints | Subtask ID | $n \le$ | $m \le$ | Subtask Dependencies | Score | | :-: | :-: | :-: | :-: | :-: | | $1$ | $10^{18}$ | $1$ | No | $1$ | | $2$ | $10$ | $4$ | No | $7$ | | $3$ | $10^5$ | $10^{18}$ | $2$ | $28$ | | $4$ | $10^{18}$ | $10^{18}$ | $1, 2, 3$ | $64$ | For all tests, it is guaranteed that: - $1 \le T \le 10$; - $3 \le n \le 10^{18}$; - $1 \le m \le 10^{18}$.