#include

#include

#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}

#define MOD 1000000007

#define sqrit(x) ((x) * (x))

using namespace std;

void fastFibo(long long int n, pair<long long int, long long int>& vals){

if(n == 0){

vals.first = 0;

vals.second = 1;

return;

}

fastFibo(n/2, vals);

long long int ev, od;

ev = 2 * vals.second - vals.first;

if(ev < 0) ev += MOD;

ev = (ev * vals.first)%MOD;

od = (sqrit(vals.first) + sqrit(vals.second))%MOD;

if(n%2 == 0){

vals.first = ev;

vals.second = od;

} else {

vals.first = od;

vals.second = od + ev;

}

}

```
int main(){
fastio
int t;
cin>>t;
pair<long long int, long long int> vals;
vals.first = vals.second = 0;
while(t--){
long long int n, x, res;
res = 0;
cin>>n>>x;
for(int i = n; i > 0; --i){
fastFibo(i, vals);
res = (x*((res + vals.first)%MOD))%MOD;
}
cout<<res<<endl;
}
return 0;
}
```