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}$.