由于 OJ 对公式渲染效果不佳，请打开链接以阅读题解：https://cloud.socoding.cn/s/WxfD?password=tower3

密码：tower3

#include <bits/stdc++.h>
#define re
using namespace std;
typedef long long ll;
#define il inline
#define sc(x) scanf("%lld",&x)
ll t, a, b, mod = 1e9 + 7;
struct matrix
{
    ll a = 0, b = 0, v[4][4] = {};
    void init(ll n)
    {
        a = b = n;
        for (ll i = 0; i < n; ++i)
        {
            v[i][i] = 1;
        }
    }
    matrix operator*(const matrix &x) const
    {
        matrix r;
        r.a = a, r.b = x.b, memset(r.v, 0, sizeof r.v);
        for (ll i = 0; i < a; ++i)
        {
            for (ll j = 0; j < x.b; ++j)
            {
                for (ll k = 0; k < b; ++k)
                {
                    (r.v[i][j] += v[i][k] * x.v[k][j]) %= mod;
                }
            }
        }
        return r;
    }
} p, q;

matrix qpow(matrix &x, ll n)
{
    matrix r;
    r.init(x.a);
    for (; n; n >>= 1)
    {
        if (n & 1)
        {
            r = r * x;
        }
        x = x * x;
    }
    return r;
}

signed main()
{
    p.v[0][0] = p.v[0][1] = p.v[1][0] = p.v[1][2] = p.v[2][0] = 1;
    q.v[0][0] = q.v[0][1] = q.v[1][0] = q.v[1][2] = 1;
    p.a = p.b = q.a = q.b = 3;
    sc(t);
    while (t--)
    {
        sc(a), sc(b);
        matrix r, c;
        c.init(3);
        r.a = 1, r.b = 3, r.v[0][0] = 2, r.v[0][1] = 1, r.v[0][2] = 1;
        ll m = (a - b) / 3, t = a % 3;
        if (t == 1)
        {
            c = p * q * q;
        }
        else if (t == 2)
        {
            c = q * p * q;
        }
        else
        {
            c = q * q * p;
        }
        c = qpow(c, m);
        r = r * c;
        printf("%lld\n", r.v[0][2 - (a - b) % 3]);
    }
    return 0;
}