# HDU 6050. Funny Function (快速幂，逆元)

## 题面

### 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


## 题解

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

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

$$\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}$$ 用快速幂计算即可。

## 代码

#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;
}