Description

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

Input Format

This problem has multiple test cases in a single test.

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case:

• The first line contains two positive integers $n$ and $m$.

Output Format

For each test case, output a line containing a non-negative integer representing the answer modulo $10^9 + 7$.

4
3 2
5 3
10 4
100000 998244353123456

4
117
430352
967771719

Hint

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

For all tests, it is guaranteed that:

• $1 \le T \le 10$;
• $3 \le n \le 10^{18}$;
• $1 \le m \le 10^{18}$.