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: #include <bits/stdc++.h>
  using namespace std;
  template <class T = int>
  using V = std::vector<T>;
  template <class T = int>
  using VV = std::vector<std::vector<T>>;
  template <class T = int>
  using VVV = std::vector<std::vector<std::vector<T>>>;
  template <class T>
  using pqup = std::priority_queue<T, std::vector<T>, std::greater<T>>;
  using ll = long long;
  using ld = long double;
  using int128 = __int128_t;
  using pii = std::pair<int, int>;
  using pll = std::pair<long long, long long>;
  using Tp = tuple<ll, ll, ll>;
  template <class T, class U>
  std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
  }
  template <class T>
  std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &i : v) is >> i;
    return is;
  }
  std::istream &operator>>(std::istream &is, __int128_t &a) {
    std::string s;
    is >> s;
    __int128_t ret = 0;
    for (int i = 0; i < s.length(); i++)
      if ('0' <= s[i] and s[i] <= '9') ret = 10 * ret + s[i] - '0';
    a = ret * (s[0] == '-' ? -1 : 1);
    return is;
  }
  namespace scanner {
  void scan(int &a) { std::cin >> a; }
  void scan(long long &a) { std::cin >> a; }
  void scan(std::string &a) { std::cin >> a; }
  void scan(char &a) { std::cin >> a; }
  void scan(char a[]) { std::scanf("%s", a); }
  void scan(double &a) { std::cin >> a; }
  void scan(long double &a) { std::cin >> a; }
  template <class T, class U>
  void scan(std::pair<T, U> &p) {
    std::cin >> p;
  }
  template <class T>
  void scan(std::vector<T> &a) {
    std::cin >> a;
  }
  void INPUT() {}
  template <class Head, class... Tail>
  void INPUT(Head &head, Tail &...tail) {
    scan(head);
    INPUT(tail...);
  }
  }  // namespace scanner
  template <class T, class U>
  std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
    os << p.first << " " << p.second;
    return os;
  }
  template <class T>
  std::ostream &operator<<(std::ostream &os, const std::vector<T> &a) {
    for (int i = 0; i < int(a.size()); ++i) {
      if (i) os << " ";
      os << a[i];
    }
    return os;
  }
  std::ostream &operator<<(std::ostream &dest, __int128_t &value) {
    std::ostream::sentry s(dest);
    if (s) {
      __uint128_t tmp = value < 0 ? -value : value;
      char buffer[128];
      char *d = std::end(buffer);
      do {
        --d;
        *d = "0123456789"[tmp % 10];
        tmp /= 10;
      } while (tmp != 0);
      if (value < 0) {
        --d;
        *d = '-';
      }
      int len = std::end(buffer) - d;
      if (dest.rdbuf()->sputn(d, len) != len) {
        dest.setstate(std::ios_base::badbit);
      }
    }
    return dest;
  }
  template <class T>
  void print(const T a) {
    std::cout << a << '\n';
  }
  template <class Head, class... Tail>
  void print(Head H, Tail... T) {
    std::cout << H << ' ';
    print(T...);
  }
  template <class T>
  void printel(const T a) {
    std::cout << a << '\n';
  }
  template <class T>
  void printel(const std::vector<T> &a) {
    for (const auto &v : a) std::cout << v << '\n';
  }
  template <class Head, class... Tail>
  void printel(Head H, Tail... T) {
    std::cout << H << '\n';
    printel(T...);
  }
  void Yes(const bool b = true) { std::cout << (b ? "Yes\n" : "No\n"); }
  void No() { std::cout << "No\n"; }
  void YES(const bool b = true) { std::cout << (b ? "YES\n" : "NO\n"); }
  void NO() { std::cout << "No\n"; }
  void err(const bool b = true) {
    if (b) {
      std::cout << "-1\n", exit(0);
    }
  }
  namespace debugger {
  template <class T>
  void view(const std::vector<T> &a) {
    std::cerr << "{ ";
    for (const auto &v : a) {
      std::cerr << v << ", ";
    }
    std::cerr << "\b\b }";
  }
  template <class T>
  void view(const std::vector<std::vector<T>> &a) {
    std::cerr << "{\n";
    for (const auto &v : a) {
      std::cerr << "\t";
      view(v);
      std::cerr << "\n";
    }
    std::cerr << "}";
  }
  template <class T, class U>
  void view(const std::vector<std::pair<T, U>> &a) {
    std::cerr << "{\n";
    for (const auto &p : a)
      std::cerr << "\t(" << p.first << ", " << p.second << ")\n";
    std::cerr << "}";
  }
  template <class T, class U>
  void view(const std::map<T, U> &m) {
    std::cerr << "{\n";
    for (const auto &p : m)
      std::cerr << "\t[" << p.first << "] : " << p.second << "\n";
    std::cerr << "}";
  }
  template <class T, class U>
  void view(const std::pair<T, U> &p) {
    std::cerr << "(" << p.first << ", " << p.second << ")";
  }
  template <class T>
  void view(const std::set<T> &s) {
    std::cerr << "{ ";
    for (auto &v : s) {
      view(v);
      std::cerr << ", ";
    }
    std::cerr << "\b\b }";
  }
  template <class T>
  void view(const T &e) {
    std::cerr << e;
  }
  }  // namespace debugger
  template <class T>
  int lb(const std::vector<T> &a, const T x) {
    return std::distance((a).begin(),
                         std::lower_bound((a).begin(), (a).end(), (x)));
  }
  template <class T>
  int ub(const std::vector<T> &a, const T x) {
    return std::distance((a).begin(),
                         std::upper_bound((a).begin(), (a).end(), (x)));
  }
  template <class T>
  void UNIQUE(std::vector<T> &a) {
    std::sort(a.begin(), a.end());
    a.erase(std::unique(a.begin(), a.end()), a.end());
  }
  template <class T>
  std::vector<T> press(std::vector<T> &a) {
    auto res = a;
    UNIQUE(res);
    for (auto &v : a) v = lb(res, v);
    return res;
  }
  template <class T>
  void ADD(std::vector<T> &a, const T x) {
    for (auto &v : a) v += x;
  }
  template <class T>
  void SUB(std::vector<T> &a, const T x = 1) {
    for (auto &v : a) v -= x;
  }
  template <class T>
  void MUL(std::vector<T> &a, const T x) {
    for (auto &v : a) v *= x;
  }
  template <class T>
  void DIV(std::vector<T> &a, const T x) {
    for (auto &v : a) v /= x;
  }
  template <class T, class U>
  inline bool chmin(T &a, const U &b) {
    return a > b ? a = b, true : false;
  }
  template <class T, class U>
  inline bool chmax(T &a, const U &b) {
    return a < b ? a = b, true : false;
  }
  template <class T>
  T divup(T x, T y) {
    return (x + y - 1) / y;
  }
  template <class T>
  T POW(T a, long long n) {
    T ret = 1;
    while (n) {
      if (n & 1) ret *= a;
      a *= a;
      n >>= 1;
    }
    return ret;
  }
  template <typename T>
  T ADD(T a, T b) {
    T res;
    return __builtin_add_overflow(a, b, &res) ? numeric_limits<T>::max() : res;
  }
  template <typename T>
  T MUL(T a, T b) {
    T res;
    return __builtin_mul_overflow(a, b, &res) ? numeric_limits<T>::max() : res;
  }
  long long POW(long long a, long long n, const int mod) {
    long long ret = 1;
    while (n) {
      if (n & 1) (ret *= a) %= mod;
      (a *= a) %= mod;
      n >>= 1;
    }
    return ret;
  }
  struct fast_io {
    fast_io() {
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      cout << fixed << setprecision(15);
    }
  } fast_io_;
  using R = long double;
  constexpr R EPS = 1E-11;
  int sgn(const R &r) { return (r > EPS) - (r < -EPS); }
  int sgn(const R &a, const R &b) { return sgn(a - b); }
  long long x10(const string &s, size_t n) {
    if (s.front() == '-') return -x10(s.substr(1), n);
    auto pos = s.find('.');
    if (pos == string::npos) return stoll(s + string(n, '0'));
    return stoll(s.substr(0, pos) + s.substr(pos + 1) +
                 string(n + pos + 1 - s.size(), '0'));
  }
  long long ceildiv(long long a, long long b) {
    if (b < 0) a = -a, b = -b;
    if (a >= 0)
      return (a + b - 1) / b;
    else
      return a / b;
  }
  long long floordiv(long long a, long long b) {
    if (b < 0) a = -a, b = -b;
    if (a >= 0)
      return a / b;
    else
      return (a - b + 1) / b;
  }
  long long floorsqrt(long long x) {
    assert(x >= 0);
    long long ok = 0;
    long long ng = 1;
    while (ng * ng <= x) ng <<= 1;
    while (ng - ok > 1) {
      long long mid = (ng + ok) >> 1;
      if (mid * mid <= x)
        ok = mid;
      else
        ng = mid;
    }
    return ok;
  }
  inline int topbit(unsigned long long x) {
    return x ? 63 - __builtin_clzll(x) : -1;
  }
  inline int popcount(unsigned long long x) { return __builtin_popcountll(x); }
  inline int parity(unsigned long long x) { return __builtin_parity(x); }
  const int inf = 1e9;
  const ll INF = 1e18;
  const ll mod = 1e9 + 7;
  struct mint {
    ll x;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint &operator+=(const mint a) {
      if ((x += a.x) >= mod) x -= mod;
      return *this;
    }
    mint &operator-=(const mint a) {
      if ((x += mod - a.x) >= mod) x -= mod;
      return *this;
    }
    mint &operator*=(const mint a) {
      (x *= a.x) %= mod;
      return *this;
    }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint val() { return x; }
    mint pow(ll t) const {
      if (!t) return 1;
      mint a = pow(t >> 1);
      a *= a;
      if (t & 1) a *= *this;
      return a;
    }
    mint inv() const { return pow(mod - 2); }
    mint &operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
  };
  istream &operator>>(istream &is, mint &a) { return is >> a.x; }
  ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }
  struct combination {
    vector<mint> fact, ifact;
    combination(ll n) : fact(n + 1), ifact(n + 1) {
      assert(n < mod);
      fact[0] = 1;
      for (ll i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
      ifact[n] = fact[n].inv();
      for (ll i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(ll n, ll k) {
      if (k < 0 || k > n) return 0;
      return fact[n] * ifact[k] * ifact[n - k];
    }
    mint p(ll n, ll k) { return fact[n] * ifact[n - k]; }
  } c(1000005);
  void main_() {
    long long N, K;
    scanner::INPUT(N, K);
    V<mint> p(30);
    p[0] = 1;
    for (int i = 0; i < (30); ++i) {
      if (i) {
        p[i] = p[i - 1] * N;
      }
    }
    mint ans = 0;
    for (ll i = 29; i >= 0; i--) {
      if ((K >> i) & 1) ans += p[i];
    }
    cout << ans << endl;
  }
  int main() {
    int t = 1;
    cin >> t;
    while (t--) main_();
    return 0;
  }
  