FIBEQN

#include <bits/stdc++.h>
#define check(N, A, B) assert((ll)(N) >= (ll)(A) && (ll)(N) <= (ll)(B))
using namespace std;
typedef long long ll;
const int mod = 1e9+7;

struct num{
    ll a,b;
  num(ll _a){
    a = _a % mod; b = 0;
  }
    num(ll _a, ll _b){
        a = _a % mod; b = _b % mod;
        if(a < 0) a += mod;
        if(b < 0) b += mod;
    }
};
inline num add(num x, num y){
    return num((x.a+y.a)%mod,(x.b+y.b)%mod);
}
inline num sub(num x, num y){
    return num((x.a-y.a+mod)%mod,(x.b-y.b+mod)%mod);
}
num mult(num x, num y){
    ll p = (x.a * y.a) % mod + (5ll * ((x.b * y.b) % mod))%mod;
    p %= mod;
    ll q = (x.a * y.b) % mod + (x.b * y.a) % mod;
    q %= mod;
    return num(p,q);
}
num exp(num x, ll n){
    num ret = num(1);
    while(n){
        if(n&1ll) ret = mult(ret,x);
        x = mult(x,x);
        n >>= 1;
    }
    return ret;
}
ll inv(ll x){
    return exp(num(x),mod-2).a;
}
num inverse(num x){
    ll c = ((x.a * x.a)%mod) - ((5ll * ((x.b * x.b)%mod))%mod);
    c %= mod;
    c = (c+mod)%mod;
    c = inv(c);
    c = (c * x.a)%mod;
    ll d = (- (x.a * x.a)%mod) + ((5ll * ((x.b * x.b)%mod))%mod);
    d %= mod;
    d = (d+mod)%mod;
    d = inv(d);
    d = (d * x.b)%mod;
    return num(c,d);
}

num gpsum(num a, ll n){
  //(a**(n+1) - 1)/(a-1)
  num ret = sub(exp(a,n+1),num(1));
  ret = mult(ret,inverse(sub(a,num(1))));
    // cout << "G: " << a.a << " " << a.b << " " << n << ": " << ret.a << " " << ret.b << endl;
  return ret;
}
ll go(ll n, ll _k){
  //Declaring Phi and Psi
  num two_inv = inverse(num(2,0));
    num phi = num(1,1);
    phi = mult(phi, two_inv);
    num psi = num(1,mod-1);
    psi = mult(psi, two_inv);
    // cout << "phi: " << phi.a << " " << phi.b << " : " << "psi: " << psi.a << " " << psi.b << endl;

  num k = num(_k);
  num ret = sub(gpsum(mult(phi,k),n), gpsum(mult(psi,k),n));
  ret = mult(ret, inverse(sub(phi,psi)));
    assert(ret.b == 0);
  return ret.a;
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int Q; cin >> Q;
  check(Q, 1, 1e9);
  while(Q--){
    ll N, K;
    cin >> N >> K;
    check(N, 1, 1e18);
    check(K, 1, 1e18);
    K %= mod;
    cout << go(N, K) << endl;
  }
}