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.OutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.OutputStream;
  import java.io.PrintWriter;
  import java.io.BufferedWriter;
  import java.util.InputMismatchException;
  import java.io.IOException;
  import java.io.Writer;
  import java.io.OutputStreamWriter;
  import java.util.BitSet;
  import java.io.InputStream;
  
  /**
   * Built using CHelper plug-in
   * Actual solution is at the top
   */
  public class Main {
      public static void main(String[] args) {
          InputStream inputStream = System.in;
          OutputStream outputStream = System.out;
          InputReader in = new InputReader(inputStream);
          OutputWriter out = new OutputWriter(outputStream);
          BSpecialNumbers solver = new BSpecialNumbers();
          solver.solve(1, in, out);
          out.close();
      }
  
      static class BSpecialNumbers {
          public void solve(int testNumber, InputReader in, OutputWriter out) {
              int mod = IntMath.pow(10, 9) + 7;
              Modular.initialize(mod);
              int t = in.nextInt();
              for (int i = 0; i < t; i++) {
                  long n = in.nextLong();
                  long k = in.nextLong();
                  // do it by bits.
                  long[] l = new long[1];
                  l[0] = k;
                  BitSet b = BitSet.valueOf(l);
                  long accum = 0;
                  for (int j = 0; j < b.length(); j++) {
                      if (b.get(j)) {
                          accum = Modular.add(accum, Modular.pow(n, j));
                      }
                  }
                  out.println(accum);
              }
          }
  
      }
  
      static final class MathPreconditions {
          static int checkNonNegative(String role, int x) {
              if (x < 0) {
                  throw new IllegalArgumentException(role + " (" + x + ") must be >= 0");
              }
              return x;
          }
  
          static long checkNonNegative(String role, long x) {
              if (x < 0) {
                  throw new IllegalArgumentException(role + " (" + x + ") must be >= 0");
              }
              return x;
          }
  
          private MathPreconditions() {
          }
  
      }
  
      static final class UnsignedLongs {
          private UnsignedLongs() {
          }
  
          private static long flip(long a) {
              return a ^ Long.MIN_VALUE;
          }
  
          public static int compare(long a, long b) {
              return Longs.compare(flip(a), flip(b));
          }
  
          public static long remainder(long dividend, long divisor) {
              if (divisor < 0) { // i.e., divisor >= 2^63:
                  if (compare(dividend, divisor) < 0) {
                      return dividend; // dividend < divisor
                  } else {
                      return dividend - divisor; // dividend >= divisor
                  }
              }
  
              // Optimization - use signed modulus if dividend < 2^63
              if (dividend >= 0) {
                  return dividend % divisor;
              }
  
              /*
               * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is
               * guaranteed to be either exact or one less than the correct value. This follows from the fact
               * that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not
               * quite trivial.
               */
              long quotient = ((dividend >>> 1) / divisor) << 1;
              long rem = dividend - quotient * divisor;
              return rem - (compare(rem, divisor) >= 0 ? divisor : 0);
          }
  
      }
  
      static final class Longs {
          private Longs() {
          }
  
          public static int compare(long a, long b) {
              return (a < b) ? -1 : ((a > b) ? 1 : 0);
          }
  
      }
  
      static final class LongMath {
          static final long FLOOR_SQRT_MAX_LONG = 3037000499L;
          private static final int SIEVE_30 = ~((1 << 1) | (1 << 7) | (1 << 11) | (1 << 13) | (1 << 17) | (1 << 19) | (1 << 23)
                  | (1 << 29));
          private static final long[][] millerRabinBaseSets = {
                  {291830, 126401071349994536L},
                  {885594168, 725270293939359937L, 3569819667048198375L},
                  {273919523040L, 15, 7363882082L, 992620450144556L},
                  {47636622961200L, 2, 2570940, 211991001, 3749873356L},
                  {
                          7999252175582850L,
                          2,
                          4130806001517L,
                          149795463772692060L,
                          186635894390467037L,
                          3967304179347715805L
                  },
                  {
                          585226005592931976L,
                          2,
                          123635709730000L,
                          9233062284813009L,
                          43835965440333360L,
                          761179012939631437L,
                          1263739024124850375L
                  },
                  {Long.MAX_VALUE, 2, 325, 9375, 28178, 450775, 9780504, 1795265022}
          };
  
          public static boolean isPrime(long n) {
              if (n < 2) {
                  MathPreconditions.checkNonNegative("n", n);
                  return false;
              }
              if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13) {
                  return true;
              }
  
              if ((SIEVE_30 & (1 << (n % 30))) != 0) {
                  return false;
              }
              if (n % 7 == 0 || n % 11 == 0 || n % 13 == 0) {
                  return false;
              }
              if (n < 17 * 17) {
                  return true;
              }
  
              for (long[] baseSet : millerRabinBaseSets) {
                  if (n <= baseSet[0]) {
                      for (int i = 1; i < baseSet.length; i++) {
                          if (!LongMath.MillerRabinTester.test(baseSet[i], n)) {
                              return false;
                          }
                      }
                      return true;
                  }
              }
              throw new AssertionError();
          }
  
          private LongMath() {
          }
  
          private enum MillerRabinTester {
              /**
               * Works for inputs ≤ FLOOR_SQRT_MAX_LONG.
               */
              SMALL {
                  long mulMod(long a, long b, long m) {
                      /*
                       * NOTE(lowasser, 2015-Feb-12): Benchmarks suggest that changing this to
                       * UnsignedLongs.remainder and increasing the threshold to 2^32 doesn't pay for itself, and
                       * adding another enum constant hurts performance further -- I suspect because bimorphic
                       * implementation is a sweet spot for the JVM.
                       */
                      return (a * b) % m;
                  }
  
  
                  long squareMod(long a, long m) {
                      return (a * a) % m;
                  }
              },
              /**
               * Works for all nonnegative signed longs.
               */
              LARGE {
                  /** Returns (a + b) mod m. Precondition: { 0 <= a}, { b < m < 2^63}. */
                  private long plusMod(long a, long b, long m) {
                      return (a >= m - b) ? (a + b - m) : (a + b);
                  }
  
                  /** Returns (a * 2^32) mod m. a may be any unsigned long. */
                  private long times2ToThe32Mod(long a, long m) {
                      int remainingPowersOf2 = 32;
                      do {
                          int shift = Math.min(remainingPowersOf2, Long.numberOfLeadingZeros(a));
                          // shift is either the number of powers of 2 left to multiply a by, or the biggest shift
                          // possible while keeping a in an unsigned long.
                          a = UnsignedLongs.remainder(a << shift, m);
                          remainingPowersOf2 -= shift;
                      } while (remainingPowersOf2 > 0);
                      return a;
                  }
  
  
                  long mulMod(long a, long b, long m) {
                      long aHi = a >>> 32; // < 2^31
                      long bHi = b >>> 32; // < 2^31
                      long aLo = a & 0xFFFFFFFFL; // < 2^32
                      long bLo = b & 0xFFFFFFFFL; // < 2^32
  
                      /*
                       * a * b == aHi * bHi * 2^64 + (aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo.
                       *       == (aHi * bHi * 2^32 + aHi * bLo + aLo * bHi) * 2^32 + aLo * bLo
                       *
                       * We carry out this computation in modular arithmetic. Since times2ToThe32Mod accepts any
                       * unsigned long, we don't have to do a mod on every operation, only when intermediate
                       * results can exceed 2^63.
                       */
                      long result = times2ToThe32Mod(aHi * bHi /* < 2^62 */, m); // < m < 2^63
                      result += aHi * bLo; // aHi * bLo < 2^63, result < 2^64
                      if (result < 0) {
                          result = UnsignedLongs.remainder(result, m);
                      }
                      // result < 2^63 again
                      result += aLo * bHi; // aLo * bHi < 2^63, result < 2^64
                      result = times2ToThe32Mod(result, m); // result < m < 2^63
                      return plusMod(result, UnsignedLongs.remainder(aLo * bLo /* < 2^64 */, m), m);
                  }
  
  
                  long squareMod(long a, long m) {
                      long aHi = a >>> 32; // < 2^31
                      long aLo = a & 0xFFFFFFFFL; // < 2^32
  
                      /*
                       * a^2 == aHi^2 * 2^64 + aHi * aLo * 2^33 + aLo^2
                       *     == (aHi^2 * 2^32 + aHi * aLo * 2) * 2^32 + aLo^2
                       * We carry out this computation in modular arithmetic.  Since times2ToThe32Mod accepts any
                       * unsigned long, we don't have to do a mod on every operation, only when intermediate
                       * results can exceed 2^63.
                       */
                      long result = times2ToThe32Mod(aHi * aHi /* < 2^62 */, m); // < m < 2^63
                      long hiLo = aHi * aLo * 2;
                      if (hiLo < 0) {
                          hiLo = UnsignedLongs.remainder(hiLo, m);
                      }
                      // hiLo < 2^63
                      result += hiLo; // result < 2^64
                      result = times2ToThe32Mod(result, m); // result < m < 2^63
                      return plusMod(result, UnsignedLongs.remainder(aLo * aLo /* < 2^64 */, m), m);
                  }
              },
              ;
  
              static boolean test(long base, long n) {
                  // Since base will be considered % n, it's okay if base > FLOOR_SQRT_MAX_LONG,
                  // so long as n <= FLOOR_SQRT_MAX_LONG.
                  return ((n <= FLOOR_SQRT_MAX_LONG) ? SMALL : LARGE).testWitness(base, n);
              }
  
              abstract long mulMod(long a, long b, long m);
  
              abstract long squareMod(long a, long m);
  
              private long powMod(long a, long p, long m) {
                  long res = 1;
                  for (; p != 0; p >>= 1) {
                      if ((p & 1) != 0) {
                          res = mulMod(res, a, m);
                      }
                      a = squareMod(a, m);
                  }
                  return res;
              }
  
              private boolean testWitness(long base, long n) {
                  int r = Long.numberOfTrailingZeros(n - 1);
                  long d = (n - 1) >> r;
                  base %= n;
                  if (base == 0) {
                      return true;
                  }
                  // Calculate a := base^d mod n.
                  long a = powMod(base, d, n);
                  // n passes this test if
                  //    base^d = 1 (mod n)
                  // or base^(2^j * d) = -1 (mod n) for some 0 <= j < r.
                  if (a == 1) {
                      return true;
                  }
                  int j = 0;
                  while (a != n - 1) {
                      if (++j == r) {
                          return false;
                      }
                      a = squareMod(a, n);
                  }
                  return true;
              }
  
          }
  
      }
  
      static final class IntMath {
          public static int pow(int b, int k) {
              MathPreconditions.checkNonNegative("exponent", k);
              switch (b) {
                  case 0:
                      return (k == 0) ? 1 : 0;
                  case 1:
                      return 1;
                  case (-1):
                      return ((k & 1) == 0) ? 1 : -1;
                  case 2:
                      return (k < Integer.SIZE) ? (1 << k) : 0;
                  case (-2):
                      if (k < Integer.SIZE) {
                          return ((k & 1) == 0) ? (1 << k) : -(1 << k);
                      } else {
                          return 0;
                      }
                  default:
                      // continue below to handle the general case
              }
              for (int accum = 1; ; k >>= 1) {
                  switch (k) {
                      case 0:
                          return accum;
                      case 1:
                          return b * accum;
                      default:
                          accum *= ((k & 1) == 0) ? 1 : b;
                          b *= b;
                  }
              }
          }
  
          private IntMath() {
          }
  
      }
  
      static class InputReader {
          private InputStream stream;
          private byte[] buf = new byte[1024];
          private int curChar;
          private int numChars;
          private InputReader.SpaceCharFilter filter;
  
          public InputReader(InputStream stream) {
              this.stream = stream;
          }
  
          public int read() {
              if (numChars == -1) {
                  throw new InputMismatchException();
              }
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      throw new InputMismatchException();
                  }
                  if (numChars <= 0) {
                      return -1;
                  }
              }
              return buf[curChar++];
          }
  
          public int nextInt() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              int res = 0;
              do {
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public long nextLong() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              long res = 0;
              do {
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public boolean isSpaceChar(int c) {
              if (filter != null) {
                  return filter.isSpaceChar(c);
              }
              return isWhitespace(c);
          }
  
          public static boolean isWhitespace(int c) {
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
  
          public interface SpaceCharFilter {
              public boolean isSpaceChar(int ch);
  
          }
  
      }
  
      static class Modular {
          public static int MOD;
          public static int SAVE_INV = 1000005;
          public static long[] save_inv = new long[SAVE_INV];
  
          public static long add(long val, long other) {
              return Math.floorMod(val + other, MOD);
          }
  
          public static long multiply(long val, long other) {
              return Math.floorMod(val * other, MOD);
          }
  
          public static void initialize(int mod) {
              MOD = mod;
              // Make sure MOD is prime, which is necessary for the inverse algorithm below.
              assert LongMath.isPrime(mod);
  
              save_inv[0] = 0;
              save_inv[1] = 1;
  
              for (int i = 2; i < SAVE_INV; i++)
                  save_inv[i] = multiply(save_inv[MOD % i], (MOD - MOD / i));
          }
  
          public static long getInverse(long val) {
              if (val < SAVE_INV)
                  return save_inv[(int) val];
  
              long product = 1;
              long v = val;
  
              while (v >= SAVE_INV) {
                  product = (long) multiply(product, MOD - MOD / v);
                  v = MOD % v;
              }
  
              return multiply(product, save_inv[(int) v]);
          }
  
          public static final long pow(long val, long k) {
              long result = 1;
              if (k < 0)
                  return pow(getInverse(val), -k);
              while (k > 0) {
                  if (k % 2 == 1)
                      result = multiply(result, val);
                  k >>= 1;
                  if (k > 0)
                      val = multiply(val, val);
              }
              return result;
          }
  
      }
  
      static class OutputWriter {
          private final PrintWriter writer;
  
          public OutputWriter(OutputStream outputStream) {
              writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
          }
  
          public OutputWriter(Writer writer) {
              this.writer = new PrintWriter(writer);
          }
  
          public void close() {
              writer.close();
          }
  
          public void println(long i) {
              writer.println(i);
          }
  
      }
  }
  
  