僅供參考

#define ll long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

const ll p = 1e9+7;

struct mtx {
    ll a, b, c;
    vector<vector<ll>> v;
    mtx(int _a, int _b, int _c):a(_a), b(_b), c(_c) {
        v.resize(3, vector<ll> (3));
        v = {
            {c, b, a},
            {1, 0, 0},
            {0, 1, 0}
        };
    }
    mtx operator* (mtx m) {
        vector<vector<ll>> mm = m.v;
        mtx res = mtx(0, 0, 0);
        vector<vector<ll>> &re = res.v;
        for(int i = 0;i < 3;i++) {
            for(int j = 0;j < 3;j++) {
                ll t = 0;
                for(int k = 0;k < 3;k++) {
                    t += v[i][k]*mm[k][j];
                    t %= p;
                }
                re[i][j] = t;
            }
        }

        return res;
    }

    ll val() {
        return v[0][0];
    }
};

mtx pw(mtx a, int b) {
    if(b == 1) return a;
    mtx tmp = pw(a, b>>1);
    return b&1?tmp*tmp*a:tmp*tmp;
}

int main() {

    fast

    int q;cin >> q;
    while(q--) {
        ll n, a, b, c;
        cin >> n >> a >> b >> c;
        if(n <= 2) cout << 0 << '\n';
        else if(n == 3) cout << 1 << '\n';
        else {
            mtx m(a, b, c);
            cout << pw(m, n-3).val() << '\n';
        }
    }

    return 0;
}