codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1594B.md (1216B)


      1 Source: https://codeforces.com/problemset/problem/1594/B
      2 
      3 B. Special Numbers
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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.
     24 
     25 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$.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     30 
     31 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$).
     32 
     33 Output
     34 
     35 For each test case, print one integer — the $k$-th special number in increasing order modulo $10^9+7$.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 3
     43 3 4
     44 2 12
     45 105 564
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 9
     52 12
     53 3595374
     54 ```
     55 
     56 Note
     57 
     58 For $n = 3$ the sequence is $[1,3,4,9...]$