Theofanis really likes sequences of positive integers, thus his teacher (Yeltsa Kcir) gave him a problem about a sequence that consists of only special numbers.

Let's call a positive number special if it can be written as a sum of different non-negative powers of $n$. For example, for $n = 4$ number $17$ is special, because it can be written as $4^0 + 4^2 = 1 + 16 = 17$, but $9$ is not.

Theofanis asks you to help him find the $k$-th special number if they are sorted in increasing order. Since this number may be too large, output it modulo $10^9+7$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first and only line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^9$; $1 \le k \le 10^9$).


-----Output-----

For each test case, print one integer — the $k$-th special number in increasing order modulo $10^9+7$.


-----Examples-----

Input
3
3 4
2 12
105 564
Output
9
12
3595374


-----Note-----

For $n = 3$ the sequence is $[1,3,4,9...]$

Difficulty: EASY
Tags: Bit manipulation

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
def ans(k, a):
	x = 0
	while k > a:
		a = a + 2 ** x
		x += 1
	k = k - 2 ** (x - 1)
	return (x - 1, k)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = 0
	y = 0
	while k != 0:
		(p, k) = ans(k, a)
		y = y + n ** p
	print(y % (10 ** 9 + 7))


mod = 10 ** 9 + 7

def func(a, b):
	result = 1
	for i in range(0, b):
		result = result * a % mod
	return result
t = int(input())
while t:
	(n, k) = map(int, input().split())
	k = bin(k)
	k = str(k)
	res = 0
	k = k[2:]
	g = len(k)
	for i in range(g - 1, -1, -1):
		if k[i] == '0':
			continue
		else:
			res = (res + func(n, g - i - 1)) % mod
	print(res)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 1:
		print(k)
		continue
	mod = 10 ** 9 + 7
	s = bin(k)[2:]
	l = len(s)
	ans = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '1':
			ans += pow(n, l - 1 - i, mod)
	print(ans % mod)


t = int(input())
mod = 10 ** 9 + 7
for i in range(t):
	(n, k) = tuple([int(x) for x in input().split()])
	solve = 0
	bits = reversed(bin(k)[2:])
	for (k, v) in enumerate(bits):
		if v == '1':
			solve += n ** k
	print(solve % mod)


ESP = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	tec = 0
	for i in bin(k)[2:]:
		tec *= n
		if i == '1':
			tec += 1
		tec %= ESP
	print(tec)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	k = list(bin(k)[2:])
	k.reverse()
	ans = 0
	for i in range(len(k)):
		ans += int(k[i]) * n ** i % (10 ** 9 + 7)
	print(ans % (10 ** 9 + 7))


import math

def base_encode(number, base):
	number = str(number).lower()
	base = int(base)
	known_digits = '0123456789abcdefghijklmnopqrstuvwxyz'
	value = {ch: val for (val, ch) in enumerate(known_digits) if val < base}
	if number[0] == '-':
		sign = -1
		number = number[1:]
	else:
		sign = 1
	total = 0
	for d in number:
		try:
			total = total * base + value[d]
		except KeyError:
			if d in known_digits:
				raise ValueError("invalid digit '{0}' in base {1}".format(d, base))
			else:
				raise ValueError('value of digit {0} is unknown'.format(d))
	return sign * total

def fun(n, k):
	a = int('{0:b}'.format(k))
	return base_encode(int(a), n) % 1000000007
tt = 0
t = int(input())
while tt < t:
	(n, k) = input().split()
	print(fun(int(n), int(k)))
	tt = tt + 1


import sys
input = sys.stdin.readline
mod = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = bin(k)[2:][::-1]
	c = len(x)
	s = 0
	for i in range(c):
		if x[i] == '1':
			s += n ** i % mod
	print(s % mod)


from math import sqrt, gcd, ceil, floor, log, factorial
from itertools import permutations, combinations
from collections import Counter, defaultdict
import collections, sys, threading
import collections, sys, threading
from bisect import *

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def msi():
	return map(str, input().split())

def li():
	return list(mi())

def foo(n, k):
	if floor(log(k, 2)) == ceil(log(k, 2)):
		return n ** floor(log(k, 2)) % mod
	return n ** floor(log(k, 2)) % mod + foo(n, k - 2 ** floor(log(k, 2)))
t = ii()
mod = 10 ** 9 + 7
for _ in range(t):
	(n, k) = mi()
	print(foo(n, k) % mod)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	w = str(bin(k))
	z = 1
	summ = 0
	for i in range(len(w)):
		if w[-1 - i] == '1':
			summ += z
		z *= n
	print(summ % (10 ** 9 + 7))


from sys import stdin
inp = stdin.readline
t = int(inp())
for _ in range(t):
	(n, k) = map(int, inp().split())
	ans = 0
	for i in range(len(bin(k)) - 1):
		mold = 2 ** i
		if k & mold:
			ans = (ans + n ** i) % (10 ** 9 + 7)
	print(ans)


from collections import deque
import bisect
import sys
input = sys.stdin.readline
M = 10 ** 9 + 7

def power(x, y):
	ans = 1
	while y > 0:
		if y % 2 == 1:
			ans = ans * x % M
		y = y // 2
		x = x * x % M
	return ans % M
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = bin(k)[2:]
	i = len(s) - 1
	ans = 0
	cnt = 0
	while i > -1:
		if s[i] == '1':
			ans = (ans + power(n, cnt)) % M
		cnt += 1
		i -= 1
	sys.stdout.write(str(ans) + '\n')


def answer(n, k):
	k = bin(k)[2:]
	l = len(k) - 1
	s = 0
	for (j, i) in enumerate(k):
		s += n ** (l - j) * int(i)
	print(s % M)
M = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	answer(n, k)


from collections import Counter, deque
import math
from random import randint
from bisect import bisect
import sys
import re
import copy
MOD = 1000000007
MAX = sys.maxsize
MIN = -sys.maxsize

class get:

	def int():
		return list(map(int, input().split()))

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

	def map():
		return map(int, input().split())

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def solve():
	(n, k) = get.map()
	bi = bin(k).replace('0b', '')
	sum_ = 0
	for i in range(len(bi) - 1, -1, -1):
		if bi[i] == '1':
			sum_ += pow(n, len(bi) - 1 - i, MOD)
			sum_ = sum_ % MOD
	print(sum_)
for _ in range(int(input())):
	solve()


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	z = k.bit_length() - 1
	ans = list('1' + '0' * z)
	if z:
		k -= pow(2, z)
		bk = bin(k)[2:]
		for i in range(len(bk)):
			ans[-(i + 1)] = bk[-(i + 1)]
	an = 0
	p = 1
	for i in range(len(ans) - 1, -1, -1):
		if ans[i] == '1':
			an = (an + p) % mod
		p = p * n % mod
	print(an)


t = int(input())
l = []
for a1 in range(t):
	x = list(map(int, input().split()))
	l.append(x)
for a2 in range(t):
	sum = 0
	b = bin(l[a2][1])
	bi = b[2:]
	bi = list(bi)
	bi = [int(item) for item in bi]
	bi = bi[::-1]
	for j in range(len(bi)):
		sum = sum + bi[j] * l[a2][0] ** j
		sum %= 10 ** 9 + 7
	print(sum)


def poww(a, b):
	res = 0
	sch = 1
	for i in range(len(a) - 1, -1, -1):
		if a[i] == '1':
			res += sch
		sch *= b
		sch %= 1000000007
	return res % 1000000007
a = int(input())
for i in range(a):
	(n, k) = map(int, input().split())
	k = bin(k)[2:]
	print(poww(k, int(n)))


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(cnt, ans) = (0, 0)
	while k:
		if k % 2:
			ans = (ans + pow(n, cnt, mod)) % mod
		cnt += 1
		k //= 2
	print(ans)


for _ in range(int(input())):
	(num, index) = map(int, input().split())
	temp = 1
	res = 0
	while index > 0:
		lol = index % 2
		index = index // 2
		if lol == 1:
			res += temp
		temp *= num
	print(res % 1000000007)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	for _ in range(1, ii() + 1):
		(n, k) = mi()
		tot = 0
		p = 1
		for i in range(31):
			if k >> i & 1:
				tot += p
				tot %= mod
			p *= n
			p %= mod
		print(tot)
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


import sys

def hp(n):
	while n % 2 == 0:
		n = n // 2
	if n == 1:
		return True
	else:
		return False
try:
	m = 10 ** 9 + 7

	def main():
		(n, k) = map(int, input().split())
		ans = 0
		x = bin(k)[2:][::-1]
		p = 1
		ans = 0
		for si in x:
			ans += p * int(si)
			p = p * n
		print(int(ans % m))
except:
	pass
for _ in range(int(input())):
	main()


t = int(input())
mod = 1000000007

def solve():
	(n, k) = map(int, input().split())
	res = 0
	for i in range(0, 32):
		if k >> i & 1:
			res = res % mod + (n % mod) ** (i % mod) % mod
	print(res % mod)
for i in range(1, t + 1):
	solve()


import bisect
import math
from collections import deque
import heapq
mod = 1000000007
N = 200005

def mul(a, b):
	return a * b % mod

def add(a, b):
	return a + b if a + b < mod else a + b - mod

def sub(a, b):
	return a - b if a - b > 0 else a - b + mod

def powr(a, b):
	ans = 1
	while b > 0:
		if b & 1:
			ans = mul(ans, a)
		a = mul(a, a)
		b //= 2
	return ans

def inv(n):
	return powr(n, mod - 2)

def factlist():
	fact = [1]
	for i in range(1, N):
		fact.append(mul(fact[i - 1], i))
	return fact

def invfactlist(fact):
	invfact = [0] * N
	invfact[0] = 1
	invfact[N - 1] = inv(fact[N - 1])
	for i in range(N - 2, 0, -1):
		invfact[i] = mul(invfact[i + 1], i + 1)
	return invfact

def rot(S):
	return list(zip(*S[::-1]))

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def generate():
	ans = [0]
	while ans[-1] < 1000000000:
		ans.append(1 + ans[-1] * 2)
	return ans

def main():
	dp = generate()
	t = int(input())
	while t:
		t -= 1
		(n, k) = map(int, input().split())
		ans = 0
		while k > 0:
			ind = bisect.bisect_right(dp, k - 1)
			p = powr(n, ind - 1)
			ans = add(ans, p)
			k -= dp[ind - 1] + 1
		print(ans)
main()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	power = 0
	result = 0
	while k > 0:
		if k % 2 == 1:
			result += n ** power
		k = k // 2
		power += 1
	print(result % (10 ** 9 + 7))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	c = 0
	ans = 0
	while k > 0:
		if k % 2:
			ans = (ans + n ** c) % 1000000007
		k //= 2
		c += 1
	print(ans)


t = int(input())
MOD = int(1000000000.0) + 7
for _ in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	p = 1
	ans = 0
	for i in range(0, 32):
		if k & 1 << i:
			ans += p
		p *= n
	print(ans % MOD)


import math

def solve(n, c):
	a = 0
	j = 1
	while c > 0:
		if c % 2 == 1:
			a = (a + j) % (10 ** 9 + 7)
		j = j * n
		c = c // 2
	print(a)
t = int(input(''))
for i in range(t):
	(a, c) = list(input('').strip().split())[:2]
	solve(int(a), int(c))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = 10 ** 9 + 7
	bink = str(bin(k))[::-1]
	ans = 0
	for i in range(len(bink)):
		if bink[i] == '1':
			ans += n ** i % p
	print(ans % p)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	c = 1
	pov = 0
	arr = []
	while k > 0:
		if c == k:
			k -= c
			arr.append(pov)
		elif c * 2 > k:
			k -= c
			arr.append(pov)
			c = 1
			pov = 0
		else:
			c *= 2
			pov += 1
	a = 0
	for ind in range(len(arr)):
		a = (a + n ** arr[ind]) % int(1000000000.0 + 7)
	print(a)


import sys
from io import BytesIO
from os import read, fstat
input = BytesIO(read(0, fstat(0).st_size)).readline

def solve_tc():
	mod = 1000000007
	(n, k) = map(int, input().split())
	s = 0
	for i in range(35):
		if k & 1 << i:
			s = (s + pow(n, i, mod)) % mod
	return s
for _ in range(int(input())):
	sys.stdout.write(str(solve_tc()) + '\n')


from math import log2
M = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	while k >= 1:
		ans = (ans + n ** int(log2(k))) % M
		k -= 2 ** int(log2(k))
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	count = 0
	for i in range(32):
		if k & 2 ** i != 0:
			count += pow(n, i, 10 ** 9 + 7)
			count %= 10 ** 9 + 7
	print(count)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	total = 0
	mod = 1000000007
	num = bin(k)[2:][::-1]
	for i in range(len(num)):
		if num[i] == '1':
			total += n ** i
	print(total % mod)


a = int(input())
l = []
for i in range(a):
	(k, n) = map(int, input().split())
	sk = 1
	ans = 0
	while n > 0:
		ans += n % 2 * sk
		n //= 2
		sk *= k
	print(ans % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	(n, k) = tuple(map(int, input().split()))
	val = 0
	adder = 1
	while k > 0:
		temp = k % 2 * adder
		val = temp + val
		k //= 2
		adder *= n
	print(val % 1000000007)


from sys import stdin

def read_input():
	(n, k) = map(int, stdin.readline().split())
	return (n, k)

def convert_to_binary(k):
	binary = []
	while k > 0:
		binary.append(k % 2)
		k //= 2
	return binary

def calc_answer(n, binary):
	answer = 0
	for (i, b) in enumerate(binary):
		if b == 1:
			answer = (answer + pow(n, i, 1000000007)) % 1000000007
	return answer

def solve(n, k):
	binary = convert_to_binary(k)
	answer = calc_answer(n, binary)
	return answer

def main():
	t = int(stdin.readline())
	for _ in range(t):
		input = read_input()
		answer = solve(*input)
		print(answer)
main()


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp_vars_int = lambda : map(int, input().split())
inp_list_int = lambda : list(map(int, input().split()))
t = int(input())
for _ in range(t):
	(n, k) = inp_vars_int()
	res = 0
	bin_k = bin(k)
	for (i, b) in enumerate(bin_k[:1:-1]):
		if b == '1':
			res += n ** i
	print(res % (10 ** 9 + 7))


t = int(input())
n = [0] * t
k = [0] * t
mod = 1000000007
for i in range(t):
	(n[i], k[i]) = map(int, input().split())
for i in range(t):
	ans = 0
	p = 1
	for j in range(33):
		if k[i] >> j & 1:
			ans += p
			ans %= mod
		p *= n[i]
	print(ans)


md = int(1000000000.0 + 7)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = bin(k)[2:][::-1]
	np = 1
	ans = 0
	for i in range(len(x)):
		if x[i] == '1':
			ans += np
			ans %= md
		else:
			pass
		np *= n
	print(int(ans))


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	sum = 0
	count = 0
	while k:
		if k % 2 == 1:
			sum += n ** count
		k = k // 2
		count += 1
	print(sum % (10 ** 9 + 7))


import collections as cc
I = lambda : list(map(int, input().split()))
mod = 10 ** 9 + 7
for tc in range(int(input())):
	(n, k) = I()
	ans = 0
	num = 1
	for i in range(0, 31):
		if k & 1 << i:
			ans = ans + pow(n, i, mod)
	print(ans % mod)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = bin(k)[2:]
	z = 0
	for i in range(len(a)):
		z = (z * n + int(a[i])) % 1000000007
	print(z)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = str(bin(k))[2:]
	x = x[::-1]
	s = 0
	count = 0
	for i in x:
		if i == '1':
			s = s + n ** count % (10 ** 9 + 7)
			count += 1
		else:
			count += 1
	print(s % (10 ** 9 + 7))


def read_nums():
	return [int(x) for x in input().split()]

def solve():
	(n, k) = read_nums()
	k_bin = bin(k)[2:]
	res = 0
	p = 1
	for ch in reversed(k_bin):
		res += int(ch) * p
		p *= n
		res = res % (1000000000 + 7)
	print(res)

def main():
	(t,) = read_nums()
	for _ in range(t):
		solve()
main()


t = int(input())
while t > 0:
	(n, k) = [int(i) for i in input().split()]
	result = 0
	power = 1
	while k > 0:
		if k % 2 == 1:
			result += power
			result %= 1000000007
		power *= n
		k = k // 2
	print(result)
	t = t - 1


MOD = 1000000007
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	digit = list(reversed(list(bin(k)[2:])))
	ans = 0
	for idx in range(len(digit)):
		if digit[idx] == '1':
			ans += n ** idx
			ans %= MOD
	print(ans)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	b = bin(k).replace('0b', '')
	ans = 0
	mod = 1000000007
	count = 0
	for i in range(len(b) - 1, -1, -1):
		if b[i] == '1':
			ans += pow(n, count, mod) % mod
		count += 1
	print(ans % mod)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	bi = bin(k)
	bi = bi[2:]
	li = [char for char in bi]
	li.reverse()
	num = 0
	for i in range(len(li)):
		if li[i] == '1':
			num += n ** i
	print(num % (10 ** 9 + 7))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	b = bin(k)[2:]
	a = 0
	p = 0
	for c in b[::-1]:
		if c == '1':
			a += n ** p
			a %= 1000000007
		p += 1
	print(a)


import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
MOD = 10 ** 9 + 7

def solve(N, K):
	res = 0
	p = 1
	while K > 0:
		if K & 1:
			res = (res + p) % MOD
		p = p * N % MOD
		K >>= 1
	return res

def main():
	T = int(input())
	for _ in range(T):
		(N, K) = list(map(int, input().split()))
		out = solve(N, K)
		output(str(out) + '\n')
main()


mod = int(1000000000.0 + 7)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	p = 1
	ans = 0
	for i in range(30):
		if k & 1 << i:
			ans = (ans + p) % mod
		p *= n
		p %= mod
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = bin(k)[2:]
	P = 1000000007
	x = list(reversed(x))
	l = len(x)
	ans = 0
	for i in range(l):
		if x[i] == '1':
			ans = ans % P + (n % P) ** i % P
	print(ans % P)


def solve():
	(n, k) = map(int, input().split())
	s = bin(k)
	s = s[2:]
	ans = 0
	md = 1000000007
	cnt = 0
	for i in range(len(s) - 1, -1, -1):
		ans = (ans + int(s[i]) * pow(n, cnt)) % md
		cnt += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

def so():
	return int(input())

def st():
	return input()

def mj():
	return map(int, input().strip().split(' '))

def msj():
	return map(str, input().strip().split(' '))

def le():
	return list(map(int, input().split()))

def lebe():
	return list(map(int, input()))

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()

def joro(L):
	return ''.join(map(str, L))

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def npr(n, r):
	return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def tir(a, b, c):
	if 0 == c:
		return 1
	if len(a) <= b:
		return 0
	if c != -1:
		return tir(a, 1 + b, c + a[b]) or tir(a, b + 1, c - a[b]) or tir(a, 1 + b, c)
	else:
		return tir(a, 1 + b, a[b]) or tir(a, b + 1, -a[b]) or tir(a, 1 + b, -1)

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
	ans = -1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	li = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, len(prime)):
		if prime[p]:
			li.append(p)
	return li

def primefactors(n):
	from math import sqrt
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def tr(n):
	return n * (n + 1) // 2

def ti(x):
	import math
	if x >= 0:
		s = math.sqrt(x)
	if s * s == x:
		return 1
	return 0
doi = int(1000000000.0 + 7)
boi = 998244353

def ryu(a, b):
	re = 1
	while b != 0:
		if b % 2 != 0:
			re *= a
			re %= boi
		b = b // 2
		a *= a
		a %= boi
	return re
fa = [0] * 100007

def pow(x, y, p):
	re = 1
	x = x % p
	while y > 0:
		if y % 2 != 0:
			re = re * x % p
		y = y // 2
		x = x * x % p
	return re

def mi(n, p):
	return pow(n, p - 2, p)

def ncr(n, r, p):
	if n < r:
		return 0
	if r == 0:
		return 1
	return fa[n] * mi(fa[r], p) % p * mi(fa[n - r], p) % p % p

def iu():
	import re
	import sys
	input = sys.stdin.readline
	import math as my
	(a, b) = mj()
	r = 1
	bec = 0
	while b != 0:
		if b % 2 == 1:
			bec += r
			bec %= doi
		b = b // 2
		r = a * r
		r = r % doi
	print(bec)

def main():
	for i in range(so()):
		iu()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
t = int(input())

def calcul(n, k):
	s = 0
	while k > 0:
		x = math.log2(k)
		p = int(x)
		c = pow(2, p)
		i = int(c * (x - p))
		s += pow(n, p)
		k -= c
		p = i
	return s % 1000000007
results = []
for i in range(t):
	(n, k) = map(int, input().split())
	results.append(calcul(n, k))
for j in results:
	print(j)


from math import log2

def solve(n, k):
	x = int(log2(k))
	ans = n ** x
	k -= 2 ** x
	if k:
		return ans + solve(n, k)
	else:
		return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(solve(n, k) % 1000000007)


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	bk = bin(k)[2:]
	ans = 0
	for i in bk:
		ans *= n
		ans %= mod
		if i == '1':
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	v = 0
	s = 0
	for i in bin(k)[:1:-1]:
		if i == '1':
			v += pow(n, s, 10 ** 9 + 7)
		s += 1
	print(v % (10 ** 9 + 7))


t = int(input())
i = 0
while i < t:
	arr = list(map(int, input().strip().split()))
	n = arr[0]
	k = arr[1]
	a = bin(k)
	b = a[2:]
	d = b[::-1]
	const = 10 ** 9 + 7
	c = len(d)
	ans = 0
	j = 0
	n1 = n
	while j < c:
		if d[j] == '1':
			ans += n ** j
		j += 1
	answer = ans % const
	print(answer)
	i += 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	k = bin(k)[2:]
	ans = 0
	for i in range(len(k)):
		if k[len(k) - 1 - i] == '1':
			ans += n ** i
	print(ans % 1000000007)


t = int(input())
for _ in range(t):
	(n, k) = [int(v) for v in input().split()]
	(ans, div) = (0, 10 ** 9 + 7)
	s = bin(k).replace('0b', '')
	for (i, c) in enumerate(s):
		if c == '1':
			ans += n ** (len(s) - i - 1) % div
			ans %= div
	print(ans)


from sys import stdout, stdin
from io import IOBase, BytesIO
from os import read, write, fstat
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size: int=...):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))

def input():
	return stdin.readline().rstrip('\r\n')
MAX_MODULE = 1000000007

def main():
	t = int(input())
	for _ in ' ' * t:
		(n, k) = map(int, input().split())
		powers = []
		idx = 0
		arr = str(bin(k))[2:][::-1]
		for s in arr:
			if s == '1':
				powers.append(idx)
			idx += 1
		answer = 0
		for i in powers:
			answer += n ** i
		print(answer % MAX_MODULE)
main()


import sys
from os import path
if path.exists('Input.txt'):
	sys.stdin = open('Input.txt', 'r')
	sys.stdout = open('Output.txt', 'w')
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin
input = stdin.buffer.readline

def solve_tc():
	(n, k) = map(int, input().split())
	s = 0
	for i in range(35):
		if k & 2 ** i:
			s = (s + n ** i) % 1000000007
	return s
for _ in range(int(input())):
	sys.stdout.write(str(solve_tc()) + '\n')


def power(n, y, m=1000000007):
	n %= m
	res = 1
	while y > 0:
		if y & 1:
			res = res * n % m
		n = n * n % m
		y >>= 1
	return res
t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	s = bin(k)
	s = s[2:]
	a = 32 - len(s)
	s = '0' * a + s
	ans = 0
	s = s[::-1]
	for i in range(32):
		if s[i] == '1':
			ans = (ans + power(n, i)) % 1000000007
	print(ans)


a = int(input())
for i in range(a):
	n = input()
	n = n.split(' ')
	er = bin(int(n[1]))
	t = er[2:len(er)]
	t = list(t)
	t.reverse()
	p = int(n[0])
	pt = 0
	for i in range(len(t)):
		pt += p ** i * int(t[i])
	print(pt % int(1000000000.0 + 7))


from collections import defaultdict, Counter, deque
from math import sqrt, log10, log, floor, factorial, gcd
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations
import sys, io, os
input = sys.stdin.readline
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
inf = float('inf')
mod = 10 ** 9 + 7

def yn(a):
	print('YES' if a else 'NO')
ceil = lambda a, b: (a + b - 1) // b
t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	bina = bin(k)[2:][::-1]
	suma = 0
	for i in range(len(bina)):
		if bina[i] == '1':
			suma += pow(n, i, mod)
			suma %= mod
	print(suma)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	r = 0
	s = 0
	count = 0
	while k:
		if k & 1:
			s += n ** count
		count += 1
		k >>= 1
	print(s % MOD)


mod = 1000000007

def solve_case():
	(n, k) = map(int, input().split())
	ans = 0
	for i in range(32):
		i_bit = 1 << i
		if k & i_bit != 0:
			ans += pow(n, i, mod)
	print(ans % mod)
T = int(input())
for t in range(T):
	solve_case()


import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	mod = 10 ** 9 + 7
	addd = 0
	while m >= 1:
		ini = 0
		count = 0
		while ini <= m:
			count += 1
			ini = 2 ** count
		count -= 1
		m -= 2 ** count
		ans = (ans + n ** count) % mod
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	k = str(bin(k)[2:])[::-1]
	ans = 0
	power = 0
	for i in k:
		if i == '1':
			ans += pow(n, power)
		power += 1
	print(ans % 1000000007)


(1, 2, 4, 8, 16)
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
(1, 3, 9, 27)
(1, 3, 4, 9, 10, 12, 13, 27)

def log2(k):
	return k.bit_length() - 1

def calc(n, k):
	if k == 0:
		return 0
	if k == 1:
		return 1
	start = log2(k)
	return calc(n, k - 2 ** start) + n ** start
T = int(input())
for t in range(T):
	(n, k) = map(int, input().split(' '))
	print(calc(n, k) % (10 ** 9 + 7))


t = int(input())
while t > 0:
	t = t - 1
	(n, k) = input().split()
	b = bin(int(k))
	b = str(bin(int(k)))[2:]
	ans = 0
	num = len(b) - 1
	for i in range(len(b)):
		if b[i] == '1':
			ans = ans + pow(int(n), num, 1000000007)
		num = num - 1
	print(ans % 1000000007)


n = int(input())
for _ in range(n):
	(base, k) = map(int, input().split())
	answer = 0
	for i in range(30):
		shifted_k = k >> i
		if shifted_k == 0:
			break
		answer += shifted_k % 2 * base ** i
	answer %= 10 ** 9 + 7
	print(answer)


def main(k):
	b = bin(k)
	b = list(b)
	b = b[::-1]
	return b
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	b = main(k)
	ans = 0
	for i in range(len(b) - 2):
		if b[i] == '1':
			ans += n ** i
	print(ans % 1000000007)


t = int(input())
for i in range(t):
	(n, k) = tuple(map(int, input().split()))
	(i, r) = (0, 0)
	while k != 0:
		if k % 2:
			r += n ** i
		i += 1
		k //= 2
	print(r % (10 ** 9 + 7), '\n')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	t = bin(k)
	(a, summa) = (t[2:], 0)
	for i in range(len(a)):
		summa += int(a[-i - 1]) * n ** i
	print(summa % (10 ** 9 + 7))


for s in [*open(0)][1:]:
	(n, k) = map(int, s.split())
	r = 0
	for x in f'{k:b}':
		r = r * n + int(x)
	print(r % (10 ** 9 + 7))


inp1 = int(input())
for i in range(inp1):
	(n, k) = map(int, input().split())
	sum = 0
	c = bin(k)
	x = [int(b) for b in str(c)[2:]]
	y = x[::-1]
	z = 1
	for a in y:
		if a == 1:
			sum += z ** a
		z *= n
	print(sum % (10 ** 9 + 7))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = 1000000000.0 + 7
	i = 0
	ans = 0
	MOD = 1000000007

	def powerLL(x, n):
		result = 1
		while n:
			if n & 1:
				result = result * x % MOD
			n = int(n / 2)
			x = x * x % MOD
		return result

	def powerStrings(sa, sb):
		a = 0
		b = 0
		for i in range(len(sa)):
			a = (a * 10 + (ord(sa[i]) - ord('0'))) % MOD
		for i in range(len(sb)):
			b = (b * 10 + (ord(sb[i]) - ord('0'))) % (MOD - 1)
		return powerLL(a, b)
	while k > 0:
		if k & 1:
			ans = (ans + powerStrings(str(n), str(i))) % m
		k = k >> 1
		i += 1
	print(int(ans))


import math
modd = 10 ** 9 + 7

def calc(r, a, b):
	ans = 0
	binn = list(reversed(bin(b)[2:].zfill(a)))
	for (i, v) in enumerate(binn):
		if v == '1':
			ans += r ** i
	return ans
t = int(input())
for _ in range(t):
	(r, k) = map(int, input().split())
	km = k
	k = k - 1
	a = math.log2(k + 1) - 1
	a = int(a)
	b = 2 ** (a + 1) - 1
	a = a + 1
	c = km - b - 1
	ans = r ** a + calc(r, a, c)
	print(int(ans % modd))


t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	(n, k) = map(int, input().split())
	base = 1
	ans = 0
	for i in range(32):
		if k & 1 << i:
			ans += base
			ans %= mod
		base *= n
		base %= mod
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	result = 0
	acc = 1
	while k > 0:
		if k & 1 == 1:
			result = (result + acc) % (10 ** 9 + 7)
		k >>= 1
		acc = acc * n % (10 ** 9 + 7)
	print(result)


from sys import stdin
input = lambda : stdin.readline().strip()
lin = lambda : list(map(int, input().split()))
iin = lambda : int(input())
main = lambda : map(int, input().split())
from math import ceil, sqrt, factorial, log
from collections import deque
from bisect import bisect_left
mod = 1000000007

def solve(we):
	(n, k) = main()
	z = bin(k)[2:]
	f = len(z) - 1
	ans = 0
	for i in range(len(z)):
		if z[i] == '1':
			ans = (ans + pow(n, f)) % mod
		f -= 1
	print(ans)
qwe = 1
qwe = iin()
for _ in range(qwe):
	solve(_ + 1)


def getlistint():
	return list(map(int, stdin.readline().split()))

def getmapint():
	return map(int, stdin.readline().split())

def getliststr():
	return list(stdin.readline().split())

def getint():
	return int(stdin.readline().strip())

def getstr():
	return stdin.readline().strip()

def pr(s):
	stdout.write(str(s) + '\n')

def prlist(l):
	stdout.write(' '.join(list(map(str, l))) + '\n')
from sys import stdin, stdout
for _ in range(getint()):
	(n, k) = getmapint()
	b = bin(k)[2:]
	s = 0
	for i in range(len(b)):
		if b[i] == '1':
			s += n ** (len(b) - 1 - i)
	pr(s % (10 ** 9 + 7))


import sys
import getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]

def solve_(n, k):
	binarr = bin(k)[2:]
	res = 0
	for c in binarr:
		res *= n
		if c == '1':
			res += 1
		res = res % M9
	return res
for case_num in range(int(input())):
	(n, k) = list(map(int, input().split()))
	res = solve(n, k)
	print(res)


t = int(input())
i = 0
while i < t:
	(n, k) = map(int, input().split())
	st = bin(k)[2:]
	st = st[::-1]
	ans = 0
	for j in range(len(st)):
		if st[j] == '1':
			ans += n ** j
	print(ans % (10 ** 9 + 7))
	i += 1


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = bin(k)[2:]
	ans = 0
	for i in range(len(s)):
		if int(s[::-1][i]):
			ans += pow(n, i, mod)
			ans %= mod
	print(ans)


modd = 1000000007

def solve():
	(n, k) = list(map(int, input().split()))
	bi = bin(k)[2:]
	return sum((pow(n, len(bi) - i - 1, modd) for i in range(len(bi)) if bi[i] == '1')) % modd
t = int(input())
while t:
	t -= 1
	print(solve())


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	res = 0
	for i in range(30, -1, -1):
		if k & 1 << i:
			k ^= 1 << i
			res += pow(n, i, mod)
			res %= mod
	print(res)


import sys
sys.setrecursionlimit(100000)

def _r():
	return sys.stdin.buffer.readline()

def rs():
	return _r().decode('ascii').strip()

def rn():
	return int(_r())

def rnt():
	return map(int, _r().split())

def rnl():
	return list(rnt())

def solve(n, k):
	mod = 10 ** 9 + 7
	p = 1
	sol = 0
	while k:
		if k & 1:
			sol = (sol + p) % mod
		p = p * n % mod
		k >>= 1
	return sol
for _ in range(rn()):
	(n, k) = rnt()
	print(solve(n, k))


inf = 10 ** 9 + 7
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = bin(k)[2:]
	ans = 0
	for i in range(len(a)):
		if a[i] == '1':
			ans += n ** (len(a) - i - 1) % inf
	print(ans % inf)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	k = bin(k)[2:]
	k = k[::-1]
	m = 1000000007
	count = 0
	for i in range(len(k)):
		if k[i] == '1':
			x = pow(n, i, m)
			count += x
			count = count % m
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	result = int()
	bin_k = bin(k)[2:][::-1]
	for index_of_bin_k in range(len(bin_k)):
		if bin_k[index_of_bin_k] == '1':
			result += n ** index_of_bin_k
	print(result % (10 ** 9 + 7))


MOD = 1000000007
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	B = bin(K)[2:][::-1]
	res = 0
	pow = 1
	for (i, w) in enumerate(B):
		if w == '1':
			res += pow
			res %= MOD
		pow *= N
		pow %= MOD
	print(res)


import sys
input = sys.stdin.readline
MODULA = 1000000000 + 7

def process(N, K):
	r = 1
	ans = 0
	i = 0
	while K > 0:
		if i > 0:
			r = r * N % MODULA
		if K & 1 == 1:
			ans = (ans + r) % MODULA
		i += 1
		K = K >> 1
	return ans
R = []
for _ in range(int(input())):
	(n, k) = map(int, input()[:-1].split())
	R.append(process(n, k))
for r in R:
	print(r)


import sys
import io, os
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.buffer.readline
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 1:
		print(1)
		continue
	table = [0] * 32
	table[0] = 1
	for i in range(1, 32):
		table[i] = table[i - 1] * n
		table[i] %= mod

	def calc(x):
		m = 1
		while 2 ** m - 1 < x:
			m += 1
		r = x - (2 ** (m - 1) - 1) - 1
		if r == 0:
			res = table[m - 1]
		else:
			res = table[m - 1] + calc(r)
		return res
	ans = calc(k)
	print(ans % mod)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	ans = c = 0
	while k > 0:
		if k % 2:
			ans = (ans + n ** c) % mod
		k //= 2
		c += 1
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
import math
from bisect import *
from heapq import *
from collections import defaultdict as dd
from collections import OrderedDict as odict
from collections import Counter as cc
from collections import deque
from itertools import groupby
sys.setrecursionlimit(20 * 20 * 20 * 20 + 10)

def solve():
	(n, k) = map(int, input().split())
	s = bin(k)[2:]
	i = 0
	t = len(s)
	l = t
	ans = 0
	while t:
		if s[l - i - 1] == '1':
			ans += pow(n, i)
		ans %= mod
		i += 1
		t -= 1
	print(ans)

def main():
	global tt
	if not ONLINE_JUDGE:
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	t = 1
	t = takein()
	for tt in range(1, t + 1):
		solve()
	if not ONLINE_JUDGE:
		print('Time Elapsed :', time.time() - start_time, 'seconds')
		sys.stdout.close()

def takein():
	return int(sys.stdin.readline().rstrip('\r\n'))

def takesr():
	return sys.stdin.readline().rstrip('\r\n')

def takeiar():
	return list(map(int, sys.stdin.readline().rstrip('\r\n').split()))

def takesar():
	return list(map(str, sys.stdin.readline().rstrip('\r\n').split()))

def takeivr():
	return map(int, sys.stdin.readline().rstrip('\r\n').split())

def takesvr():
	return map(str, sys.stdin.readline().rstrip('\r\n').split())

def PrimeChecker(a):
	if a > 1:
		for j in range(2, int(a / 2) + 1):
			if a % j == 0:
				return False
				break
		else:
			return True
	else:
		return False

def ispalindrome(s):
	return s == s[::-1]

def invert(bit_s):
	temp = int(bit_s, 2)
	inverse_s = temp ^ 2 ** (len(bit_s) + 1) - 1
	rslt = bin(inverse_s)[3:]
	return str(rslt)

def counter(a):
	q = [0] * max(a)
	for i in range(len(a)):
		q[a[i] - 1] = q[a[i] - 1] + 1
	return q

def counter_elements(a):
	q = dict()
	for i in range(len(a)):
		if a[i] not in q:
			q[a[i]] = 0
		q[a[i]] = q[a[i]] + 1
	return q

def string_counter(a):
	q = [0] * 26
	for i in range(len(a)):
		q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
	return q

def factorial(n, m=1000000007):
	q = 1
	for i in range(n):
		q = q * (i + 1) % m
	return q

def factors(n):
	q = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			q.append(i)
			q.append(n // i)
	return list(sorted(list(set(q))))

def prime_factors(n):
	q = []
	while n % 2 == 0:
		q.append(2)
		n = n // 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			q.append(i)
			n = n // i
	if n > 2:
		q.append(n)
	return list(sorted(q))

def transpose(a):
	(n, m) = (len(a), len(a[0]))
	b = [[0] * n for i in range(m)]
	for i in range(m):
		for j in range(n):
			b[i][j] = a[j][i]
	return b

def power_two(x):
	return x and (not x & x - 1)

def ceil(a, b):
	return -(-a // b)

def seive(n):
	a = [1]
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p = p + 1
	for p in range(2, n + 1):
		if prime[p]:
			a.append(p)
	return a

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def binary_search(li, val):
	ans = -1
	lb = 0
	ub = len(li) - 1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	q = str(bin(k))
	q = q[2:len(q)]
	ans = 0
	l = len(q)
	for i in range(l):
		ans += int(q[i]) * n ** (l - i - 1)
	print(ans % (10 ** 9 + 7))


import sys
inp = sys.stdin.readline()
test = int(inp.strip('\n'))
result = ''
for i in range(test):
	inp = sys.stdin.readline()
	(n, k) = list(map(int, inp.strip('\n').split()))
	val = bin(k).lstrip('0b')
	size = len(val)
	num = 0
	for i in range(size):
		if val[i] == '1':
			num = num + n ** (size - 1 - i)
	num %= 1000000000 + 7
	sys.stdout.write(str(num) + '\n')


t = int(input())
for b in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	cnter = 1
	while k > 0:
		if k % 2 == 1:
			ans += cnter
		cnter *= n
		k //= 2
	print(ans % 1000000007)


mod = 10 ** 9 + 7

def solve(st, base):
	start = 0
	ans = 0
	for i in st[::-1]:
		if i == '1':
			ans += base ** start % mod
		start += 1
	return ans % mod

def fun(ls):
	(base, k) = ls
	summ = 0
	count = -1
	if k == 1:
		print(1)
		return
	while summ < k:
		count += 1
		summ += 2 ** count
	last = 2 ** count
	if summ == k:
		last_add = 2 ** count
		current = summ - last_add
		in_bin = k - current - 1
		bn = bin(in_bin)[2:]
		st = '1' + (count - len(bn)) * '0' + bn
		print(solve(st, base))
	else:
		last_add = 2 ** count
		current = summ - last_add
		in_bin = k - current - 1
		bn = bin(in_bin)[2:]
		st = '1' + (count - len(bn)) * '0' + bn
		print(solve(st, base))
T = int(input())
for i in range(T):
	ls = list(map(int, input().split()))
	fun(ls)


import sys
import math
__ = int(sys.stdin.readline())
for _ in range(__):
	(n, k) = map(int, sys.stdin.readline().split())
	b = bin(k)
	s = b[2:]
	ans = 0
	x = len(s)
	for i in range(x):
		if s[i] == '1':
			ans = ans + n ** (x - 1 - i)
	print(ans % 1000000007)


def decimalToBinary(n):
	return bin(n).replace('0b', '')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	binary = decimalToBinary(k)
	result = 0
	binary = binary[::-1]
	for i in range(len(binary)):
		if binary[i] == '1':
			result += n ** i
	print(result % 1000000007)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = bin(k)[2:]
	sm = 0
	for i in range(len(st) - 1, -1, -1):
		if st[i] == '1':
			sm += n ** (len(st) - 1 - i)
	print(sm % (10 ** 9 + 7))


import sys
input = sys.stdin.readline
rep = int(input())
po = []
for i in range(31):
	po.append((2 ** i, i))
po.reverse()
result = []
for _ in range(rep):
	(a, b) = map(int, input().split())
	result = []
	for i in po:
		if b < i[0]:
			continue
		b -= i[0]
		result.append(a ** i[1])
	print(sum(result) % (int(1000000000.0) + 7))


m = pow(10, 9) + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = 1
	res = 0
	for i in range(0, 32):
		if 1 << i > k:
			break
		if k & 1 << i:
			res = (res + p) % m
		p *= n
		p %= m
	print(res)


from sys import stdin
from bisect import bisect_left

def solve():
	results = []
	MOD = 10 ** 9 + 7
	pow_of_2 = []
	x = 1
	while x < 10 ** 9:
		pow_of_2.append(x)
		x *= 2
	for _ in range(int(stdin.readline().strip())):
		(n, k) = map(int, stdin.readline().strip().split())
		ans = 0
		while k:
			pos = bisect_left(pow_of_2, k)
			if pos == len(pow_of_2):
				pos -= 1
			if pow_of_2[pos] > k:
				pos -= 1
			ans += pow(n, pos, MOD)
			k -= pow_of_2[pos]
		results.append(ans % MOD)
	print('\n'.join(map(str, results)))
solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict, Counter, deque
from math import sqrt, log10, log, floor, factorial, gcd
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations
import sys, io, os
input = sys.stdin.readline
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
inf = float('inf')
mod = 10 ** 9 + 7

def yn(a):
	print('YES' if a else 'NO')
ceil = lambda a, b: (a + b - 1) // b
t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	bina = bin(k)[2:][::-1]
	suma = 0
	for i in range(len(bina)):
		if bina[i] == '1':
			suma = (suma + pow(n, i, mod)) % mod
	print(suma)


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import *
from collections import defaultdict, deque, Counter
import math, string
from heapq import *
from operator import add
from itertools import accumulate
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inf = float('inf')
en = lambda x: list(enumerate(x))
ceil_ = lambda a, b: (a + b - 1) // b
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
mod = 10 ** 9 + 7

def solve():
	(n, k) = r()
	k = bin(k)[2:][::-1]
	c = 0
	for (i, j) in enumerate(k):
		if int(j):
			c = (c + pow(n, i, mod)) % mod
	print(c)
for _ in ' ' * ii():
	solve()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	st = bin(k)[2:]
	cnt = 1
	ans = 0
	for j in range(len(st) - 1, -1, -1):
		ans += int(st[j]) * cnt
		cnt *= int(n)
	print(ans % 1000000007)


import math
t = int(input())
for i in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	s = 0
	while k != 0:
		p = math.log(k) / math.log(2)
		p = int(p)
		s += n ** p
		k -= 2 ** p
	print(s % int(1000000000.0 + 7))


import itertools
from collections import defaultdict
import itertools
import math
import sys
import bisect
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

def li():
	return [int(i) for i in input().split()]

def lli(rows):
	return [li() for _ in range(rows)]

def si():
	return input()

def ii():
	return int(input())

def ins():
	return input().split()
mod = 10 ** 9 + 7

def solve():
	(n, k) = LI()
	s = bin(k).lstrip('0b')[::-1]
	p = 1
	ans = 0
	for si in s:
		if si == '1':
			ans = (ans + p) % mod
		p = p * n % mod
	return ans

def main():
	for _ in range(II()):
		sys.stdout.write(str(solve()) + '\n')
main()


from collections import Counter
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	b = bin(k)[2:]
	ans = 0
	for i in range(len(b) - 1, -1, -1):
		if b[i] == '1':
			ans = (ans + n ** (len(b) - 1 - i)) % 1000000007
	print(ans)


t = int(input())
a = []
for i in range(0, 31):
	a.append(2 ** i)

def find(k, l, r):
	while l <= r:
		x = (l + r) // 2
		if a[x] <= k:
			l = x + 1
			kq = x
		else:
			r = x - 1
	return (a[kq], kq)

def doing(k, n):
	(val, neark) = find(k, 0, 30)
	if val == k:
		return n ** neark
	else:
		return n ** neark + doing(k - val, n)
for i in range(t):
	s = input()
	n = int(s[0:s.find(' ')])
	k = int(s[s.find(' ') + 1:])
	print(doing(k, n) % 1000000007)


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys
import heapq

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = get_ints()
	mod = 10 ** 9 + 7
	ans = 0
	for i in range(32):
		if k & 1 << i > 0:
			ans += pow(n, i, mod)
			ans %= mod
	print(ans)


t = int(input())
mod = 1000000007
for _ in range(t):
	(n, k) = map(int, input().split())
	radix2 = []
	while True:
		if k == 1:
			radix2.append(1)
			break
		temp = k % 2
		radix2.append(temp)
		k = k // 2
	l = len(radix2)
	pown = [1]
	ans = 0
	for i in range(1, l):
		pown.append(pown[i - 1] * n % mod)
		if radix2[i]:
			ans += pown[i]
	if radix2[0]:
		ans += 1
	print(ans % mod)


mod = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	r = 0
	p = 1
	for i in range(31):
		if k & 1 << i:
			r = int((r + p) % mod)
		p = int(p * n % mod)
	print(r)


from math import ceil, log, floor
from collections import defaultdict, deque
import sys
import os.path
sys.setrecursionlimit(200000)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r+')
	sys.stdout = open('output.txt', 'w')

def MI():
	return map(int, input().split())
mod = 10 ** 9 + 7

def solve():
	(n, k) = MI()
	ans = 0
	while k > 0:
		r = 0
		for i in range(0, 34):
			if 2 ** i > k:
				break
			r = i
		ans += n ** r % mod
		k -= 2 ** r
	print(ans % mod)
t = int(input())
for _ in range(t):
	solve()


t = int(input())
while t:
	arr = [int(a) for a in input().split()]
	(n, k) = arr
	bi = '{0:b}'.format(k)
	j = len(bi) - 1
	ans = 0
	for i in range(len(bi)):
		if bi[i] == '1':
			ans += pow(n, j, 1000000007)
		j -= 1
	print(ans % 1000000007)
	t -= 1


mod = 10 ** 9 + 7
for i in range(int(input())):
	(n, k) = map(int, input().split())
	b = bin(k)[2:]
	ans = 0
	p = 0
	for j in b[::-1]:
		if j == '1':
			ans = (ans + pow(n, p, mod)) % mod
		p += 1
	print(ans)


t = int(input())
for t1 in range(t):
	l = list(map(int, input().split()))
	ans = 0
	for i in range(31, -1, -1):
		if l[1] & 1 << i != 0:
			ans += l[0] ** i
	ans = ans % (10 ** 9 + 7)
	print(ans)


max_value = 10 ** 9 + 7

def special_number(n, k):
	b = bin(k).replace('0b', '')
	i = len(b)
	result = 0
	for index in range(len(b)):
		i -= 1
		result = result + int(b[index]) * n ** i
		index += 1
		if result > max_value:
			result = result % max_value
	return result
t = int(input())
for _ in range(0, t):
	(n, k) = map(int, input().split(' '))
	print(special_number(n, k))


m = int(input())
for i in range(m):
	[n, k] = list(map(int, input().split(' ')))
	a = int(bin(k).replace('0b', ''))
	r = 0
	k = 1
	while a > 0:
		if a % 2 == 1:
			r += k
		k = k * n
		a = a // 10
	print(r % 1000000007)


def recursion(n, k):
	if k == 1:
		return 1
	else:
		r = 0
		while 2 ** r - 1 < k:
			r += 1
		if k - 2 ** (r - 1) == 0:
			return n ** (r - 1)
		else:
			return n ** (r - 1) + recursion(n, k - 2 ** (r - 1))
T = int(input())
while T:
	(n, k) = map(int, input().split())
	print(recursion(n, k) % (10 ** 9 + 7))
	T -= 1


import io, os
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, namedtuple
from math import gcd, ceil, floor
from itertools import combinations, permutations
input = sys.stdin.buffer.readline

def work(n, k):
	mod = 10 ** 9 + 7
	s = bin(k)
	s = s[2:]
	m = len(s)
	ans = 0
	for i in range(m):
		if s[i] == '1':
			ans = (ans + pow(n, m - i - 1, mod)) % mod
	print(ans)
	return

def main():
	test = int(input())
	for idt in range(test):
		(n, k) = map(int, input().split())
		work(n, k)
	return
main()


from __future__ import division, print_function
import bisect
import collections
import math
import os
import sys
from io import BytesIO, IOBase
from typing import Counter, Deque
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
MOD = 1000000007

def main():
	t = int(input())
	while t:
		(n, k) = map(int, input().split())
		b = bin(k)
		s = str(b[2:])
		ans = 0
		for (i, v) in enumerate(s):
			if v == '1':
				ans += pow(n, len(s) - i - 1) % MOD
		print(ans % MOD)
		t -= 1
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import math
from collections import Counter
input = sys.stdin.readline
N = int(1000000000.0 + 7)
for _ in range(int(input().strip())):
	(n, k) = [int(j) for j in input().strip().split()]
	b = [0 for i in range(50)]
	count = 0
	t = 1
	a = []
	while k:
		if k % 2 == 0:
			k //= 2
			count += 1
		elif k % 2 == 1:
			k -= 1
			b[count] += 1
			if b[count] > 1:
				t = 0
		else:
			print(-1)
			t = 0
		if t != 0:
			for i in range(50):
				if b[i] > 0:
					a.append(i)
	a = list(set(a))
	ans = 0
	for i in a:
		ans += pow(n, i, N)
	print(ans % N)


MOD: int = int(1000000000.0 + 7)

def main() -> None:
	t: int = int(input())
	for i in range(t):
		run()

def run() -> None:
	(n, k) = map(int, input().split())
	print(sum((pow(n, i, MOD) if 1 << i & k else 0 for i in range(32))) % MOD)
main()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = []
	while k > 0:
		arr.append(k % 2)
		k //= 2
	res = 0
	s = 1
	for i in arr:
		if i:
			res += s
			res %= 1000000007
		s *= n
	print(res)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(k, n) = map(int, input().split())
	ans = 0
	s = bin(n)
	n = len(s)
	x = 1
	for i in range(n - 1, 1, -1):
		ans = (ans + int(s[i]) * x) % mod
		x = x * k % mod
	print(ans)


mod = 10 ** 9 + 7

def modPow(x, y):
	if y == 0:
		return 1
	if y == 1:
		return x % mod
	f = modPow(x, y // 2) % mod
	f = f * f % mod
	if y % 2 == 0:
		return f
	else:
		return x * f % mod
for tc in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	sum = 0
	for i in range(31):
		if 1 << i & k != 0:
			sum = (sum + modPow(n, i)) % mod
	print(sum)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ans = 0
	temp = 2 ** 32
	m = 32
	while temp != 0:
		if temp & k != 0:
			ans += n ** m
		temp = temp >> 1
		m -= 1
	print(ans % (int(1000000000.0) + 7))


from sys import stdin
from math import log2
for testcase in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	KthSpecialNumber = 0
	while k:
		nextNPowerInKthTerm = int(log2(k))
		KthSpecialNumber += n ** nextNPowerInKthTerm
		k -= 2 ** nextNPowerInKthTerm
	print(KthSpecialNumber % (10 ** 9 + 7))


from bisect import insort, bisect_right, bisect_left
from sys import stdout, stdin, setrecursionlimit
from heapq import heappush, heappop, heapify
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def getPrimes(N=10 ** 5):
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n, prime=getPrimes()):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
num = getInt()
for _ in range(num):
	(n, k) = zzz()
	ans = 0
	p = 1
	for i in range(31):
		if k & 1 << i:
			ans = (ans + p) % mod
		p *= n
		p %= mod
	print(ans)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	ans = 0
	(x, y) = (1, 3)
	num = 2
	if b == 1:
		print(1)
	elif b == 2:
		print(a)
	else:
		while y < b:
			(x, y) = (y, 2 * y + 1)
			num += 1
		b = bin(b)[2:]
		for i in b:
			num -= 1
			ans += int(i) * pow(a, num)
		print(ans % 1000000007)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	for (p, x) in enumerate(reversed(bin(k)[2:])):
		ans += int(x) * n ** p
	print(ans % (10 ** 9 + 7))


import sys
from os import path
if path.exists('Input.txt'):
	sys.stdin = open('Input.txt', 'r')
	sys.stdout = open('Output.txt', 'w')
input = lambda : sys.stdin.readline().rstrip()

def solve_tc():
	(n, k) = map(int, input().split())
	k = list(bin(k))[:1:-1]
	sum = 0
	for i in range(len(k)):
		if int(k[i]):
			sum += n ** i
			sum = sum % 1000000007
	return sum
for _ in range(int(input())):
	sys.stdout.write(str(solve_tc()) + '\n')


MOD = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	for digit in bin(k):
		ans *= n
		if digit == '1':
			ans += 1
		ans %= MOD
	print(ans)


import sys
inp = sys.stdin.readline
MOD = int(1000000000.0 + 7)
for i in range(int(inp())):
	(n, k) = map(int, inp().split())
	r = 0
	for j in range(30):
		if k >> j & 1:
			r = (r + pow(n, j, MOD)) % MOD
	print(r)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(k, n) = map(int, input().split())
	x = bin(n)[2:][::-1]
	s = 0
	for i in range(len(x)):
		if x[i] == '1':
			s = (s + pow(k, i, MOD)) % MOD
	print(s)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	binary_k = list((int(x) for x in bin(k)[2:]))
	binary_k = list(reversed(binary_k))
	ans = 0
	max_len = len(binary_k)
	for j in range(max_len):
		if binary_k[j] == 1:
			ans += n ** j
	print(ans % (7 + 10 ** 9))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(bin(k))[2:]
	o = 0
	m = 10 ** 9 + 7
	for i in range(len(s)):
		o += n ** i % m * (int(s[-(i + 1)]) % m)
		o = o % m
	print(int(o % m))


for _ in range(int(input().strip())):
	(n, k) = list(map(int, input().strip().split()))
	num = bin(k)[2:]
	ans = 0
	for i in range(len(num)):
		ans = (ans * n + int(num[i])) % 1000000007
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	mod = 1000000007
	ans = 0
	for i in range(30):
		if k & 1 << i:
			ans += pow(n, i)
	print(ans % mod)


t = int(input())
MOD = 10 ** 9 + 7
for _ in range(t):
	(n, c) = map(int, input().split())
	s = 0
	count = 0
	while c:
		if c & 1:
			s += n ** count
		count += 1
		c >>= 1
	print(s % MOD)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007
for _ in range(stdint()):
	(n, k) = stdmap()
	b = bin(k)[2:]
	b = b[::-1]
	res = 0
	for i in range(len(b)):
		if b[i] == '1':
			res = (res + pow(n, i, mod)) % mod
	print(res % mod)


class Comba:

	def __init__(self, mod):
		self.fact = array.array('i', [0] * MX)
		self.fact[0] = 1
		self.fact_inv = array.array('i', [0] * MX)
		self.mod = mod
		for i in range(1, MX):
			self.fact[i] = self.fact[i - 1] * i % self.mod
		self.fact_inv[MX - 1] = pow(self.fact[MX - 1], self.mod - 2, self.mod)
		for i in range(MX - 2, -1, -1):
			self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod

	def ncr(self, n, r):
		if r > n or n < 0 or r < 0:
			return 0
		return self.fact[n] * self.fact_inv[r] % self.mod * self.fact_inv[n - r] % self.mod

	def npr(self, n, r):
		if r > n or n < 0 or r < 0:
			return 0
		return self.fact[n] * self.fact_inv[n - r] % self.mod

def lcm(a, b):
	return a * b // gcd(a, b)

def rw_file():
	sys.stdin = open('', 'r')
	sys.stdout = open('', 'w')

def re(data=str):
	return data(sys.stdin.readline().rstrip())

def mp(data=str):
	return map(data, sys.stdin.readline().split())
import sys, array
from bisect import bisect_left, bisect_right, insort_left
from math import ceil, floor, log, sqrt, gcd
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify
(mod, mod9, nl, MX) = (1000000007, 998244353, '\n', 200003)

def solve(tc):
	(n, k) = mp(int)
	ans = 0
	for m in range(43):
		if 1 << m & k:
			ans = (ans + n ** m) % mod
	print(ans)
	return None

def main():
	tests = 1
	tests = re(int)
	for case in range(1, tests + 1):
		solve(case)
main()


MOD = 10 ** 9 + 7

def kth_special_number(k, n):
	ans = 0
	base = 1
	for i in range(32):
		ans = (ans % MOD + (k & 1 << i != 0) * base % MOD) % MOD
		base *= n
	return ans % MOD
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(kth_special_number(k, n))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	b = str(bin(k))[2:]
	p = 0
	ans = 0
	for i in b[::-1]:
		if i == '1':
			ans += n ** p
		p += 1
	print(ans % (7 + 10 ** 9))


def main():
	tc = 1
	tc = int(input())
	for _ in range(tc):
		(n, k) = map(int, input().split())
		n = int(n)
		cnt = 0
		s = bin(k).replace('0b', '')
		s = s[::-1] + '0' * 32
		for i in range(32):
			if s[i] == '1':
				cnt = (cnt + pow(n, i)) % (10 ** 9 + 7)
		print(cnt)
main()


from sys import stdin, stdout, setrecursionlimit
from io import BytesIO, IOBase
setrecursionlimit(10000)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			a = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not a:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(a), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			a = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = a.count(b'\n') + (not a)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(a), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
input = lambda : stdin.readline().rstrip('\r\n')
inp = lambda : int(input())
st = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
int_arr = lambda : list(map(int, input().strip().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().strip().split())
get_int = lambda : map(int, input().strip().split())
get_float = lambda : map(float, input().strip().split())
mod = 1000000007

def binpow(a, b, mod):
	a %= mod
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % mod
		a = a * a % mod
		b >>= 1
	return res
for _ in range(inp()):
	(n, k) = get_int()
	val = bin(k)[2:]
	tot = 0
	l = len(val)
	for i in range(l - 1, -1, -1):
		if val[i] == '1':
			tot = (tot + binpow(n, l - 1 - i, mod)) % mod
	print(tot)


t = int(input())
o = 0
while o != t:
	o += 1
	(n, k) = map(int, input().split())
	k_2 = ''
	while k >= 2:
		k_2 = str(k % 2) + k_2
		k = k // 2
	k_2 = str(k) + k_2
	sum = 0
	for i in range(len(k_2) - 1, -1, -1):
		if k_2[i] == '1':
			sum += n ** (len(k_2) - 1 - i)
	print(sum % (10 ** 9 + 7))


import math
for i in range(int(input())):
	(n, K) = map(int, input().split())
	k = bin(K)[2:]
	a = 0
	for q in range(len(k) - 1, -1, -1):
		if k[q] == '1':
			a += n ** (len(k) - q - 1)
	z = 10 ** 9 + 7
	print(a % z)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	i = 0
	m = 10 ** 9 + 7
	a = 0
	p = 1
	while i < 31:
		if k & 1 << i:
			a = (a + p) % m
		p *= n
		p = p % m
		i += 1
	print(a)


def L():
	return list(map(int, input().split()))

def I():
	return int(input())

def solve():
	(n, x) = map(int, input().split())
	bini = bin(x)
	cout = 0
	ans = 1
	for x in bini[2:][::-1]:
		if x == '1':
			ans += n ** cout
			ans = ans % 1000000007
		cout += 1
	print(ans - 1)
for _ in range(int(input())):
	solve()


from sys import stdin
input = stdin.readline
test = int(input())
for _ in range(test):
	(n, k) = map(int, input().split())
	(arr, total, mod) = ([], 0, 1000000007)
	while k != 0:
		arr.append(k % 2)
		k = k // 2
	prev = 1
	for v in arr:
		total = (total + prev * v) % mod
		prev = prev * n % mod
	print(total)


def solve():
	mod = 10 ** 9 + 7
	(n, k) = list(map(int, input().split()))
	ans = 0
	idx = 0
	while k:
		if k & 1:
			ans += n ** idx
		k = k >> 1
		idx += 1
	print(ans % mod)
for _ in range(int(input())):
	solve()


mod = 10 ** 9 + 7
t = int(input())
cp = [1]
for _ in range(30):
	cp.append(cp[-1] * 2)
for _ in range(t):
	(n, k) = map(int, input().split())
	pw = [1]
	ans = 0
	for _ in range(30):
		pw.append(pw[-1] * n % mod)
	for i in range(30, -1, -1):
		if cp[i] <= k:
			k -= cp[i]
			ans += pw[i]
	print(ans % mod)


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = 0
	p = 0
	while k != 0:
		if k % 2:
			a = (a + n ** p) % (10 ** 9 + 7)
			k = k // 2
		else:
			k = k // 2
		p += 1
	print(a)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 1000000007
	num = 0
	while k > 0:
		x = int(math.log(k, 2))
		x %= mod
		c = n ** x % mod
		num += c
		k -= 2 ** x
	print(num % mod)


counter = int(input())
for i in range(counter):
	(a, n) = map(int, input().split())
	k = bin(n)
	k = str(k)
	lis = list(k)
	del lis[0]
	del lis[0]
	leng = len(lis)
	op = 0
	for i in range(leng):
		if lis[leng - i - 1] == '1':
			op += a ** i
	print(int(op % int(1000000000.0 + 7)))


m = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	b = bin(k)[2:][::-1]
	count = 0
	a = 0
	for i in b:
		if i == '1':
			count = (count + pow(n, a, m)) % m
		a += 1
	print(count)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = bin(k)[2:]
	su = 0
	lens = len(s)
	for i in range(lens):
		if s[i] == '1':
			su += n ** (lens - i - 1)
	print(su % mod)


t = int(input())
biggie = 10 ** 9 + 7
for _ in range(t):
	nk = str(input()).split()
	n = int(nk[0])
	k = int(nk[1])
	k_mod_2 = []
	while k != 0:
		k_mod_2.append(k % 2)
		k = k // 2
	number = []
	for i in range(len(k_mod_2)):
		number.append(k_mod_2[i] * n ** i)
	print(sum(number) % biggie)


n = int(input())
a = []
for i in range(n):
	b = []
	y = 0
	x = list(map(int, input().split()))
	while x[1] > 0:
		for k in range(10 ** 7):
			if x[1] < 2 ** k:
				b.append(k - 1)
				x[1] = x[1] - 2 ** (k - 1)
				break
	for j in range(len(b)):
		y += x[0] ** b[j]
	if y > 10 ** 9 + 7:
		y = y % (10 ** 9 + 7)
	a.append(y)
for i in range(n):
	print(a[i])


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = bin(k).replace('0b', '')
	t = len(a)
	ans = 0
	for j in range(t):
		if a[j] == '1':
			ans = ans + n ** (t - j - 1)
	print(ans % 1000000007)


def intlog2(n):
	(j, p) = (1, 0)
	while 2 * j <= n:
		j *= 2
		p += 1
	return (p, j)

def term(n, k):
	if k < 1:
		return 0
	(x, y) = intlog2(k)
	return (pow(n, x, M) + term(n, k - y)) % M
t = int(input())
M = 10 ** 9 + 7
for case in range(t):
	(n, k) = (int(x) for x in input().split())
	print(term(n, k))


n = int(input())
for _ in range(n):
	(base, k) = map(int, input().split())
	bin_k = bin(k)[2:]
	len_bin_k = len(bin_k)
	answer = 0
	for i in range(len_bin_k):
		answer += base ** (len_bin_k - i - 1) * int(bin_k[i])
	answer %= 10 ** 9 + 7
	print(answer)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	k = inputs[1]
	bin1 = bin(k)
	if bin1[len(bin1) - 1] == '0':
		num = 0
	else:
		num = 1
	pro = n
	for i in range(len(bin1) - 2, 1, -1):
		num += int(bin1[i]) * pro
		pro = pro * n
	print(num % 1000000007)


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
maxn = 10 ** 9 + 7
for _ in range(inp()):
	(n, k) = invr()
	nc = n
	s = [0] * 31
	idx = -1
	while k > 0:
		s[idx] = k % 2
		k = k // 2
		idx -= 1
	s = list(reversed(s))
	ans = 0
	for i in range(len(s)):
		v = 1
		for j in range(i):
			v = v * n % maxn
		ans = (ans + v * s[i]) % maxn
	print(ans)


import math
MOD = 1000000007
t = int(input())
while t:
	(n, k) = map(int, input().strip().split())
	special_num = 0
	temp = 1
	while k > 0:
		if k & 1 == 1:
			special_num = (special_num + temp) % MOD
		k = k >> 1
		temp = temp * n % MOD
	print(special_num)
	t -= 1


import math

def bin(n):
	list1 = []
	if n == 0:
		list1.append(0)
		return list1
	while n > 1:
		list1.append(n % 2)
		n = n // 2
	list1.append(1)
	return list1
listout = []
test = int(input())
m = 1000000007
while test > 0:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	listk = bin(k)
	count = 0
	for x in range(len(listk)):
		count = count + int(n ** x) * listk[x]
	count = count % m
	listout.append(int(count))
	test = test - 1
for x in listout:
	print(x)


M = 1000000007
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	c = ans = 0
	x = 1
	while k:
		if k & 1:
			ans = (ans + x) % M
		c += 1
		k >>= 1
		x = x * n % M
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	print(sum([pow(n, i) for i in range(30) if k & 1 << i]) % (10 ** 9 + 7))


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	ans = 0
	x = 0
	while k:
		if k & 1:
			ans = ans + n ** x
			x += 1
			k = k >> 1
		else:
			x += 1
			k = k >> 1
	print(ans % 1000000007)


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
MOD = 10 ** 9 + 7
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
m = 10 ** 9 + 7

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		k = bin(k)[::-1]
		k = k[:-2]
		s = 0
		j = 0
		for i in k:
			s += int(i) * n ** j
			s %= m
			j += 1
		print(s)
main()


import sys
readline = sys.stdin.readline
T = int(readline())
for _ in range(T):
	(N, K) = map(int, readline().split())
	mod = 10 ** 9 + 7
	lst = [1]
	for i in range(35):
		lst.append(lst[-1] * N % mod)
	ans = 0
	for i in range(35):
		if K >> i & 1:
			ans += lst[i]
			ans %= mod
	print(ans)


times = input()
for i in range(int(times)):
	ans = 0
	data = input()
	(n, k) = data.split()
	n = int(n)
	k = list(bin(int(k)))
	k = k[2:]
	tmp = len(k)
	for i in range(tmp):
		if k[i] == '1':
			ans = ans + n ** (tmp - i - 1)
	print(ans % 1000000007)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	temp = bin(k).replace('0b', '')[::-1]
	ans = 0
	for i in range(len(temp)):
		if temp[i] == '1':
			ans += pow(n, i, mod)
			ans %= mod
	print(ans)


const = 10 ** 9 + 7

def max_k(n, k):
	q = bin(k)[2:]
	result = 0
	for i in range(len(q)):
		cur = q[-i - 1]
		temp = n ** i * int(cur)
		result += temp
	return int(result % const)
t = int(input())
pairs = []
for i in range(t):
	pairs.append(list(map(int, input().split())))
for i in range(t):
	(n, k) = pairs[i]
	print(max_k(n, k))