Chef is playing a game on the non-negative x-axis. It takes him $1$ second to reach from $i^{th}$ position to $(i-1)^{th}$ position or $(i+1)^{th}$ position. The chef never goes to the negative x-axis. Also, Chef doesn't stop at any moment of time.
The movement of chef can be described as follows.
- At the start he is standing at $x=0$ at time $0$.
- In the first round, he moves towards $x=1$ and comes back to the $x=0$ position. 
- In the second round, he moves towards the $x=2$ and comes back again to $x=0$. 
- Generalizing, in the $k^{th}$ round, he moves from $x=0$ to $x=k$ and then returns back to $x=0$ at the end of the round. This goes on as the game progresses.
For Example, the path of Chef for $3^{rd}$ round is given below.
$0 - 1 - 2 - 3 - 2 - 1 - 0$ 
The overall path followed by Chef would look somewhat like this:
$0 - 1 - 0 - 1 - 2 - 1 - 0 - 1 - 2 - 3 - 2 - 1 - 0 - 1 - 2 - 3 - 4 - 3 - …$
You are given two non-negative integers $N$ and $K$. You have to tell the time at which Chef arrives at $x=N$ for the $K^{th}$ time. 
Note - Chef can not skip a position while visiting the positions.

-----Input:-----
- The first line contains $T$ the number of test cases. Then the test cases follow.
- Each test case contains a single line of two integers $N$ and $K$.

-----Output:-----
For each test case, print a single line containing one integer -- the time taken by the chef to arrive at $x=N$ for the $K^{th}$ time by modulo $1,000,000,007$.

-----Constraints-----
- $1 \le T \le 10^5$
- $0 \le N \le 10^9$
- $1 \le K \le 10^9$

-----Sample Input:-----
5
0 1
1 1
2 1
1 3
4 6

-----Sample Output:-----
0
1
4
5
46

-----Explanation:-----
Test Case 1:

Chef starts the journey from the $N = 0$ at time $t = 0$ and it's the first time $(K = 1)$, he is here. So, the answer is $0$.  
Test Case 2:

Chef starts the journey from the $N = 0$ at time $t = 0$ then goes to $N = 1$ at $t = 1$ and it's the first time $(K = 1)$, he is here. So, the answer is $1$.
Test Case 4:

The path followed by Chef to reach $1$ for the third time is given below.
$0 - 1 - 0 - 1 - 2 - 1$

He reaches $1$ for the third time at $t=5$.

Difficulty: interview

Starter code:

Solutions:
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    from math import ceil
    t = I()
    l = []
    for _ in range(t):
        n,k=MI()
        if n==0:
            k-=1
            ans = ((k)*((k+1)))%mod
            l.append(ans)
        else:
            # if k==1:
            #     ans = ((((n)*((n-1)))%mod)+ n%mod)%mod
            #     l.append(ans)
            # else:
            #     k-=1
            #     lr = (n%mod+((ceil(k/2)%mod))%mod
            #     ans = ((lr*((lr-1))%mod
            #     if k%2!=0:
            #         ans= (ans%mod + n%mod)%mod
            #     else:
            #         ans = ((ans%mod)+((lr+n)%mod))%mod
            #     l.append(ans)
            if k%2!=0:
                lr = k//2
                l.append(((n*n)%mod+(lr*((2*n)%mod))%mod+(lr*(lr+1))%mod)%mod)
            else:
                lr = k//2
                l.append(((n*n)%mod + (lr*(2*n)%mod)%mod + (lr*(lr-1))%mod)%mod)

    for i in range(t):
        pf(str(l[i]))

def __starting_point():
    main()
__starting_point()

for i in range(int(input())):
    n,k = list(map(int,input().split()))  
    if n==0 and k==1 :
        print(0)
    
    elif n==0:
        print((k*(k-1))%q)
    else:
        m = n+1
        q= 10**9+7
        if k%2 ==0:
            m+=k//2-1
            print((m**2+n-m)%q)
        else:
            m+=(k+1)//2-1
            print((m**2-n-m)%q)
    


for _ in range(int(input())):
    n,k = list(map(int,input().split()))
    if n == 0:
        print((k*(k-1))%1000000007)
    elif k == 1:
        print((n**2)%1000000007)
    else:
        turn = (k//2)
        point = turn + n
        if k%2 == 0:
            print((point**2 - turn)%1000000007)
        else:
            print((point**2 + turn)%1000000007)
            
    
    
                
                
                


try:
    t=int(input())
    for _ in range(t):
        a,b=map(int,input().split())
        if(a==0):
            print(((b-1)*b)%1000000007)
        else:
            c=b%2
            if(c==0):
                x=(b-2)//2
                ans=(a+x)*(a+x+1)+a
                print(ans%1000000007)
            else:
                x=b//2
                ans=(a+x-1)*(a+x)
                ans=(ans+a+2*x)
                print(ans%1000000007)
except:
    pass

for _ in range(int(input())):
    n,k = map(int,input().split()) ; m =(10**9)+7
    if n==0:
        if k==1:
            print(0)
        else:
            print((k*(k-1))%m)
    else:
        if k==1:
            print((n*(n-1)+n)%m)
        elif k%2:
            x = n+((k-1)//2)
            print((x*(x+1)-n)%m)
        else:
            x = (n+(k//2))
            print((x*(x-1)+n)%m)

t = int(input().strip())
m = 1000000007
for _ in range(t):
    n,k = [int(x) for x in input().strip().split()]
    if n==0:
        ans = (k*(k-1))%m
    elif k%2==0:
        ans = ((n*n)%m + (k*n)%m + (((k)*(k-2))//4)%m)%m
    else:
        ans = ((n*n)%m + ((k-1)*n)%m + (((k+1)*(k-1))//4)%m)%m
    print(ans)

# cook your dish here
try:
    t=int(input())
    for _ in range(t):
        x,y=map(int,input().split())
        if(x==0):
            print(((y-1)*y)%1000000007)
        else:
            inc=y%2
            if(inc==0):
                cir=(y-2)//2
                a=(x+cir)*(x+cir+1)+x
                print(a%1000000007)
            else:
                cir=y//2
                a=(x+cir-1)*(x+cir)
                a=(a+x+2*cir)
                print(a%1000000007)
except:
    pass

for t in range(int(input())):
    n,k=map(int,input().split())
    mod=10**9+7
    if n==0:
        if k==1:
            print(0)
        else:
            print(k*(k-1)%mod)
    else:
        if k%2==0:
            a=n+k//2-1
            print((a*(a+1)+n)%mod)
        else:
            a=n+k//2    
            print((a*(a+1)-n)%mod)

'''input
6
0 1
1 1
2 1
1 3
4 6
4 100
'''
from bisect import bisect_left as bl, bisect_right as br
from collections import defaultdict as dd
mod=10**9+7

for _ in range(int(input())):

    #n=int(input())
    n,k=list(map(int,input().strip().split()))
    if(k==1):
        sm=pow(n,2,mod)
        print(sm)
        continue
    elif(n==0):
        sm=k*(k-1)
        print(sm%mod)
        continue
    else:
        sm=(n*(n+1))%mod


    y=(k-1)/2
    q=y
    if(int(y)==y):
        y=max(0,int(y)-1)
        rem=2
    else:
        y=int(y)
        rem=1
    
    sm+=(2*y*n)%mod+(y*(y+1))%mod
    #print(sm,"**")

    if(rem==1):
        sm+=n
    else:
        sm+=2*(n+y+1)-n

    print(sm%mod)





# cook your dish here
md=1000000007
for tst in range(int(input())):
    n,k = [int(x) for x in input().split()]
    if(n==0):
        ans=(k*(k-1))%md
        print(ans)
        continue
    z=0
    if (k&1):
        z=1
    g=(k//2)+n
    ans=((g+1)*g)
    if(z):
        ans=(ans-n)%md
    else:
        ans=(ans-g-g+n)%md
    print(ans)

# cook your dish here
try:
    t=int(input())
    for _ in range(t):
        a,b=map(int,input().split())
        if(a==0):
            print(((b-1)*b)%1000000007)
        else:
            inc=b%2
            if(inc==0):
                cir=(b-2)//2
                ans=(a+cir)*(a+cir+1)+a
                print(ans%1000000007)
            else:
                cir=b//2
                ans=(a+cir-1)*(a+cir)
                ans=(ans+a+2*cir)
                print(ans%1000000007)
except:
    pass

for i in range(int(input())):
    n,k=map(int,input().split())
    if(n!=0):
        d=(k-1)//2
        z=n**2+(k//2)*(2*n)+d*(d+1)
        z=z%(10**9+7)
        print(z)
    else:
        z=k*(k-1)
        z=z%(10**9+7)
        print(z)

import math
mod=(10**9)+7
T=int(input())
for _ in range(T):
    N,K=list(map(int,input().split()))
    if (N==0):
        print(((K*(K-1)))%mod)
    else:
        pos=(math.ceil((K-1)/2)+N)
        if ((K)%2==0 or K==1):
            et=N
        else:
            et=pos+pos-N
        t=((pos*(pos-1))+et)%mod
        print(t%mod)


t=int(input())
for hh in range(0,t):
    n,k=[int(x) for x in input().split()]
    # 2 3
    m=1000000007
    pos=n
    if(n==0):
        rem=k-1
        cur=(rem*(rem+1))%m
        print(cur)
    elif(k==1):
        prev=(pos*(pos-1))%m
        curr=(prev+pos)%m
        print(curr)
    else:
        # if(k%2==1):
        #     p=k//2
        #     # p=1
        #     inipos=pos
        #     pos=pos+p-1
        #     prev=pos*(pos+1)
        #     print(prev,pos)
        #     curr=prev+inipos
        #     print(curr)
        # else:
        #     p=k//2 -1 
        #     inipos=pos
        #     # pos=4 k = 6 p=2
        #     pos=pos+p-1
        #     prev=pos*(pos+1)
        #     now=inipos+p
        #     rem=now-inipos
        #     print(prev,now,pos,p,rem)
        #     curr=prev+now+rem
        #     print(curr)
        if(k%2==1):
            k-=1
            p=k//2
            # p=1
            ans=2*pos
            inipos=pos
            # pos=4 k = 6 p=2
            pos=(pos+p-1)%m
            prev=(pos*(pos+1))%m
            now=(inipos+p)%m
            rem=(now-inipos+m)%m
            # print(prev,now,pos,p,rem)
            curr=(prev+now+rem)%m
            print(curr)
        else:
            k-=1
            p=k//2
            # p=1
            # pos =4 k =6 k=5 p=2
            inipos=pos
            pos=(pos+p)%m
            prev=(pos*(pos+1))%m
            # print(prev,pos)
            curr=(prev+inipos)%m
            print(curr)

# cook your dish here
t=int(input())
M=1000000007
for z in range(t):
    N,K=list(map(int,input().split()))
    if N==0:
        K=K-1
        t=(K*(K+1))%M
        print(t)
        continue
    if K%2==0:
        s=N+K//2-1
        t=((s*(s+1))%M+N)%M
    else:
        s=N+K//2
        t=((s*(s+1))%M-N)%M
    print(t)

for i in range(int(input())):
    n,k=map(int,input().split())
    if(n!=0):
        d=(k-1)//2
        z=n**2+(k//2)*(2*n)+d*(d+1)
        z=z%(10**9+7)
        print(z)
    else:
        z=k*(k-1)
        z=z%(10**9+7)
        print(z)

from math import *
t=int(input())
p=1000000007
while(t):
    t-=1
    x,k=list(map(int,input().split()))
    y=ceil(k/2)
    if(x==0):
        if(k==1):
            print(0)
            continue
        k-=1
        y=(k*(k+1))
        y=y//2
        y=y*2
        print(y%p)
        continue
    if(k==1):
        print((x*x)%p)
    elif(k==2):
        z=x*x
        z+=2*x
        print(z%p)
    elif(k%2):
        minus=(x*(x+1))
        minus=minus//2
        fi=x*x
        y=x+(k//2)
        fac=((y*(y+1))//2)
        fac-=minus
        fac=fac*2
        fi+=fac
        print(fi%p)
    else:
        minus=(x*(x+1))
        minus=minus//2
       # print(minus)
        se=(x*x)+(2*x)
        y=x+((k-1)//2)
        fac=((y*(y+1))//2)
        #print(fac)
        fac-=minus
        fac=fac*2
        se+=fac
        print(se%p)

        


from math import *
t=int(input())
p=10**9+7
for i in range(t):
    
    
    n,k=list(map(int,input().split()))
    ans=(n+ceil((k-1)/2))%p
    r=ans
    
    ans=(((((ans+1)*(ans))//2)*2))%p
    
    
    if(k==0):
        print(0)
        continue
    k=k-1
    if(n==0):
        print((((k*(k+1))//2)*2)%p)
        continue

    if(k!=0):
        if(k%2==0):
            ans=ans-(r-(r-n))
        
        else:
            ans=ans-r-(r-n)
    else:
        ans=ans-r
    print(ans%p)


# cook your dish here
t=int(input())
for i in range(t):
    a,b=input().split()
    a,b=int(a),int(b)
    if a==0:
        b=b*2
    ans=pow(a,2)+int(b/2)*2*a+pow(int(b/2)-1,2)+int(b/2)-1
    if b%2!=0:
        ans=ans+b-1
    print(ans%1000000007)

def solve(n,k):
    ans=0
    if n==0:
        if k==1:
            return 0
        else:
            ans=(k-1) * (k)
            return ans%1000000007
    if k==1:
        return (n*n)%1000000007
    if k%2==0:
        ans= n*n + n*k + int(int((k-1)/2) * int((k-1)/2 + 1))
    if k%2!=0:
        ans= n*n + (2*n)*(max(0,int((k-1)/2))) + int(int((k-1)/2) * int((k-1)/2 + 1))
    return ans%1000000007

t=int(input())
for qw in range(t):
    n,k=list(map(int, input().split()))
    print(solve(n,k))


for t in range(int(input())):
    n,k=map(int,input().split())
    mod=10**9+7
    if n==0:
        if k==1:
            print(0)
        else:
            print(k*(k-1)%mod)
    else:
        if k%2==0:
            a=n+k//2-1
            print((a*(a+1)+n)%mod)
        else:
            a=n+k//2    
            print((a*(a+1)-n)%mod)

import math
for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    t = math.floor(k/2)
    r = n + t
    s = r*(r+1)
    if k % 2 == 1:
        s -= n
    else:
        s = s - r
        s = s - t
    if n == 0:
        k = k - 1 
        s = int(k*(k+1))
    print(s % 1000000007)


# cook your dish here
import sys
msg = sys.stdin.readlines()

l=[]

for i in msg:
    l.append (list (map (int, i.split())))
    
sm = lambda x: int(x*(x+1)*1)

def timew (n, k):
    if n==0:
        time = sm(k-1)
    else:
        if k == 1:
            time = (n-1)*(n) + n
        else:
            if k%2==1:
                pre_rounds = (k-1)//2
                time = sm(n+pre_rounds-1) + n + 2*(pre_rounds)
            else:
                pre_rounds = (k)//2
                time = sm(n+pre_rounds-1) + n
    return time%1000000007
    
for i in l[1:]:
    [n, k] = i
    print(timew (n, k))

#This code sucks, you know it and I know it.  
#Move on and call me an idiot later.

t = int(input())
while t:
	n, k = map(int, input().split())
	x = k // 2
	
	if(n == 0):
		print(k * (k-1) % 1000000007)
	else:
		if(k%2 == 0):
			print(((n + x)*(n + x) - x) % 1000000007)
		else:
			print(((n + x)*(n + x) + x) % 1000000007)
	t -= 1