#include"bits/stdc++.h"
using namespace std;
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int unsigned long long int
#define mod 1000000007ull
int32_t main()
{
FASTIO
int t;
cin>>t;
while(t--)
{
int n,k,s=0ull;
cin>>n>>k;
if(n==0)
s = (k*(k-1ull))%mod;
else
{
if(k==1)
s = ((n*(n-1ull))%mod + n)%mod;
else if(k%2==0)
{
int gf = n + k/2ull;
s = ((gf*(gf-1ull))%mod + n)%mod;
}
else
{
int wf = n + k/2ull;
s = (((wf*(wf+1ull))%mod - wf)%mod + (wf-n)%mod)%mod ;
}
}
cout<<s<<'\n';
}
return 0;
}
I2luY2x1ZGUiYml0cy9zdGRjKysuaCIKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBGQVNUSU8gaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwojZGVmaW5lIGludCB1bnNpZ25lZCBsb25nIGxvbmcgaW50CiNkZWZpbmUgbW9kIDEwMDAwMDAwMDd1bGwKaW50MzJfdCBtYWluKCkKewoJRkFTVElPCglpbnQgdDsKCWNpbj4+dDsKCXdoaWxlKHQtLSkKCXsKCQlpbnQgbixrLHM9MHVsbDsKCQljaW4+Pm4+Pms7CgkJaWYobj09MCkKCQkJcyA9IChrKihrLTF1bGwpKSVtb2Q7CgkJZWxzZQoJCXsKCQkJaWYoaz09MSkKCQkJcyA9ICAoKG4qKG4tMXVsbCkpJW1vZCArIG4pJW1vZDsKCQkJZWxzZSBpZihrJTI9PTApCgkJCXsKCQkJCWludCBnZiA9IG4gKyBrLzJ1bGw7CgkJCQlzID0gKChnZiooZ2YtMXVsbCkpJW1vZCArIG4pJW1vZDsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCWludCB3ZiA9IG4gKyBrLzJ1bGw7CgkJCQlzID0gKCgod2YqKHdmKzF1bGwpKSVtb2QgLSB3ZiklbW9kICsgKHdmLW4pJW1vZCklbW9kIDsKCQkJfQoJCX0KCQkKCQkKCQljb3V0PDxzPDwnXG4nOwoJfQoJcmV0dXJuIDA7Cn0=