description: 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 ≤ t ≤ 10^4) — the number of test cases.
  
  The first and only line of each test case contains two integers n and k (2 ≤ n ≤ 10^9; 1 ≤ k ≤ 10^9).
  
  Output
  
  For each test case, print one integer — the k-th special number in increasing order modulo 10^9+7.
  
  Example
  
  Input
  
  
  3
  3 4
  2 12
  105 564
  
  
  Output
  
  
  9
  12
  3595374
  
  Note
  
  For n = 3 the sequence is [1,3,4,9...]
solution: 
  import java.io.*;
  import java.util.*;
  public class cp
  {
  	static class Reader {
  		final private int BUFFER_SIZE = 1 << 16;
  		private DataInputStream din;
  		private byte[] buffer;
  		private int bufferPointer, bytesRead;
  
  		public Reader()
  		{
  			din = new DataInputStream(System.in);
  			buffer = new byte[BUFFER_SIZE];
  			bufferPointer = bytesRead = 0;
  		}
  
  		public Reader(String file_name) throws IOException
  		{
  			din = new DataInputStream(
  					new FileInputStream(file_name));
  			buffer = new byte[BUFFER_SIZE];
  			bufferPointer = bytesRead = 0;
  		}
  
  		public String readLine() throws IOException
  		{
  			byte[] buf = new byte[64]; // line length
  			int cnt = 0, c;
  			while ((c = read()) != -1) {
  				if (c == '\n') {
  					if (cnt != 0) {
  						break;
  					}
  					else {
  						continue;
  					}
  				}
  				buf[cnt++] = (byte)c;
  			}
  			return new String(buf, 0, cnt);
  		}
  
  		public int nextInt() throws IOException
  		{
  			int ret = 0;
  			byte c = read();
  			while (c <= ' ') {
  				c = read();
  			}
  			boolean neg = (c == '-');
  			if (neg)
  				c = read();
  			do {
  				ret = ret * 10 + c - '0';
  			} while ((c = read()) >= '0' && c <= '9');
  
  			if (neg)
  				return -ret;
  			return ret;
  		}
  
  		public long nextLong() throws IOException
  		{
  			long ret = 0;
  			byte c = read();
  			while (c <= ' ')
  				c = read();
  			boolean neg = (c == '-');
  			if (neg)
  				c = read();
  			do {
  				ret = ret * 10 + c - '0';
  			} while ((c = read()) >= '0' && c <= '9');
  			if (neg)
  				return -ret;
  			return ret;
  		}
  
  		public double nextDouble() throws IOException
  		{
  			double ret = 0, div = 1;
  			byte c = read();
  			while (c <= ' ')
  				c = read();
  			boolean neg = (c == '-');
  			if (neg)
  				c = read();
  
  			do {
  				ret = ret * 10 + c - '0';
  			} while ((c = read()) >= '0' && c <= '9');
  
  			if (c == '.') {
  				while ((c = read()) >= '0' && c <= '9') {
  					ret += (c - '0') / (div *= 10);
  				}
  			}
  
  			if (neg)
  				return -ret;
  			return ret;
  		}
  
  		private void fillBuffer() throws IOException
  		{
  			bytesRead = din.read(buffer, bufferPointer = 0,
  					BUFFER_SIZE);
  			if (bytesRead == -1)
  				buffer[0] = -1;
  		}
  
  		private byte read() throws IOException
  		{
  			if (bufferPointer == bytesRead)
  				fillBuffer();
  			return buffer[bufferPointer++];
  		}
  
  		public void close() throws IOException
  		{
  			if (din == null)
  				return;
  			din.close();
  		}
  	}
  	
  	/* Iterative Function to calculate (x^y) in O(log y) */
  	  static long power(long x, long y, long p)
  	  {
  	    long res = 1; // Initialize result
  	 
  	    x = x % p; // Update x if it is more than or
  	    // equal to p
  	 
  	    if (x == 0)
  	      return 0; // In case x is divisible by p;
  	 
  	    while (y > 0)
  	    {
  	 
  	      // If y is odd, multiply x with result
  	      if ((y & 1) != 0)
  	        res = (res * x) % p;
  	 
  	      // y must be even now
  	      y = y >> 1; // y = y/2
  	      x = (x * x) % p;
  	    }
  	    return res;
  	  }
  	  
  	  static int power(int x,int y) {
  		  if(y == 0) {
  			  return 1;
  		  }
  		  if(y % 2 == 0) {
  			  int temp = power(x,y/2)%1000000007;
  			  return temp*temp%1000000007;
  			  
  		  }else {
  			  return ((x%1000000007)*power(x,y-1))%1000000007;
  		  }
  		  
  	  }
  	  
  
  
  	public static void main(String[] args) throws IOException
  	{	
  
  		try{
  			//Your Solve
  			Reader s = new Reader();
  			//			Scanner s = new Scanner(System.in);
  			int t = s.nextInt();
  			for(int p = 0;p < t;p++) {
  				int n = s.nextInt();
  				int k = s.nextInt();
  				String str = Integer.toBinaryString(k);
  //				System.out.println(str);
  				long ans = 0;
  //				double check = 0;
  				for(int i = 0;i < str.length();i++) {
  //					check += (str.charAt(i)-'0')*Math.pow(n,str.length()-1 - i);
  					ans += ((str.charAt(i)-'0')*power(n,str.length()-1 - i,1000000007))%1000000007;
  //					System.out.println(power(n,str.length()-1));
  //					System.out.println(ans);
  				}
  				System.out.println(ans%1000000007);
  //				System.out.println(power(n,9,1000000007));
  			}
  
  		}catch(Exception e){
  			return;
  		}
  	}
  }