题面

Description

Function $F_{x,y}$ satisfies:

$$ F_{1, 1} = F_{1, 2} = 1 \\ F_{1, i} = F_{1, i - 1} + 2 * F_{1, i - 2} \; (i \geq 3) \\ F_{i, j} = \sum_{k = j}^{j + N - 1}F_{i - 1, k} \; (i \geq 2, j \geq 1) $$

For given integers $N$ and $M$,calculate $F_{m, 1}$ modulo $10^{9} + 7$.

Input

There is one integer T in the first line.

The next T lines,each line includes two integers N and M .

1<=T<=10000,1<=N,M<2^63.

Output

For each given N and M,print the answer in a single line.

Sample Input

2
2 2
3 3

Sample Output

2
33

题解

记 $F_{1, i}$ 为 $a_{i}$ ,则

$$ a_{i} = a_{i - 1} + 2a_{i - 2} \; (i \geq 3) $$

设 $p \neq 0, q \in \mathbb{R}$ 使得

$$ a_{i} + ka_{i - 1} = p(a_{i - 1} + ka_{i - 2}) $$

两式对照并解得 $\left \{ \begin{matrix} p = -1 \\ k = -2 \end{matrix} \right.$ 或 $\left \{ \begin{matrix} p = 2 \\ k = 1 \end{matrix} \right.$ .

  • $\left \{ \begin{matrix} p = -1 \\ k = -2 \end{matrix} \right.$ 成立

此时记 $b_{i - 1} = a_{i} - 2a_{i - 1}$ ,易得

$$ b_{i} = (-1)^{i} $$

故 $a_{i} - 2a_{i - 1} = (-1)^{i - 1}$ . 此时有

$$ \frac{a_{i}}{(-1)^{i}}+2\frac{a_{i - 1}}{(-1)^{i - 1}} = -1 $$

记 $c_{i} = \dfrac{a_{i}}{(-1) ^ {i}}$ ,易得

$$ c_{i} = \frac{1}{3}(-2)^{i} - \frac{1}{3} $$

$$ a_{i} = (-1)^{i}c_{i} = \frac{2^{i}}{3} + \frac{(-1)^{i - 1}}{3} $$

  • $\left \{ \begin{matrix} p = 2 \\ k = 1 \end{matrix} \right.$ 成立

易知此时亦有 $a_{i} = \dfrac{2^{i}}{3} + \dfrac{(-1)^{i - 1}}{3}$ 成立。

综上,此时有

$$ F_{1, i} = \frac{1}{3} \cdot (-1)^{i - 1} + \frac{1}{3} \cdot 2^{i} \tag{1} $$

此时考虑

$$ F_{2, i} = \sum_{k=i}^{i+N-1}F_{1,k}=\sum_{k=1}^{i+N-1}F_{1,k}-\sum_{k=1}^{i-1}F_{1,k} \tag{2} $$

又,此时有

$$ \sum_{i=1}^{n}F_{1,i} = \frac{1}{3}\sum_{i=1}^{n}(-1)^{i-1}+\frac{1}{3}\sum_{i=1}^{n}2^{i} \\ =\frac{1}{6}\cdot(1+(-1)^{n+1})+\frac{2}{3}\cdot(2^{n}-1) $$

代入 $(2)$ 式可得

$$ F_{2, i} = \frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)\cdot2^{i} \tag{3} $$

类似地,易得

$$ F_{3,i}=\frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)^{2}\cdot2^{i} \tag{4} $$

此时,由归纳法易证

$$ F_{m,i}=\frac{1}{3}\cdot\frac{(-1)^{i+N}-(-1)^{i}}{2}+\frac{1}{3}\cdot(2^{N}-1)^{m-1}\cdot2^{i} \tag{5} $$

因此

$$ F_{m,1}=\frac{1}{3}[(m\;\mathbf{mod}\;2)+2\cdot(2^{N}-1)^{m-1}] \tag{6} $$

用快速幂计算即可。

代码

此题 $N$ 和 $M$ 都是 $2^{63}$ 范围,因此要用 unsigned long long

模 $k$ 乘法千万不能忘了逆元。。。这次居然很脑抽地居然把逆元忘了导致赛中自闭orz = =

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const ull MODULO = 1e9 + 7;

ull power(ull a, ull b, ull p);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);

    int t = 0;
    cin >> t;

    while (t--) {
        ull n = 0, m = 0;
        cin >> n >> m;

        if (m == 1) {
            cout << 1 << endl;
            continue;
        }

        ull x1 = n & 1;
        ull x2 = (2 * power(power(2, n, MODULO) - 1, m - 1, MODULO)) % MODULO;

        ull ans = (x1 + x2) * 333333336 % MODULO;

        cout << ans << endl;
    }

    return 0;
}

ull power(ull a, ull b, ull p) {
    ull ans = 1 % p;

    for (; b; b >>= 1) {
        if (b & 1)
            ans = (ull)ans * a % p;
        a = (ull)a * a % p;
    }

    return ans;
}

preView