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...]$