Problem:


Score : 300 points

Problem Statement

          Eli- 1 started a part-time job handing out leaflets for N seconds. 
          Eli- 1 wants to hand out as many leaflets as possible with her special ability, Cloning.  
          Eli- gen can perform two kinds of actions below. 
	

 Clone herself and generate Eli- (gen + 1) .  (one Eli- gen (cloning) and one Eli- (gen + 1) (cloned) exist as a result of Eli-gen 's cloning.)
            This action takes gen \times C ( C is a coefficient related to cloning. ) seconds. 

 Hand out one leaflet. This action takes one second regardress of the generation ( =gen ). 

          They can not hand out leaflets while cloning. 
          Given N and C , find the maximum number of leaflets Eli- 1 and her clones can hand out in total modulo 1000000007 (= 10^9 + 7). 
	

Constraints

 1 \leq Q \leq 100000 = 10^5 

 1 \leq N_q \leq 100000 = 10^5 

 1 \leq C_q \leq 20000 = 2 \times 10^4 

Input

The input is given from Standard Input in the following format: 

Q
N_1 C_1
:
N_Q C_Q

The input consists of multiple test cases. On line 1 ,  Q that represents the number of test cases is given. 
            Each test case is given on the next Q lines.
            For the test case q ( 1 \leq q \leq Q ) , N_q and 
            C_q are given separated by a single space. 
            N_q and C_q represent the working time and the coefficient related to cloning for test case q respectively. 
	  

Output

            For each test case, Print the maximum number of leaflets Eli- 1 and her clones can hand out modulo 1000000007 ( = 10^9 + 7 ). 
	

Partial Scores

 30 points will be awarded for passing the test set satisfying the condition: Q = 1 . 

Another 270 points will be awarded for passing the test set without addtional constraints and you can get 300 points in total. 

Sample Input 1

2
20 8
20 12

Sample Output 1

24
20

 For the first test case, while only 20 leaflets can be handed out without cloning,
	  24 leaflets can be handed out by cloning first and two people handing out12 leaflets each. 

 For the second test case, since two people can only hand out 8 leaflets each if Eli- 1 clones, she should hand out 20 leaflets without cloning. 

Sample Input 2

1
20 3

Sample Output 2

67

One way of handing out 67 leaflets is like the following image. Each black line means cloning, and each red line means handing out. 

 This case satisfies the constraint of the partial score. 

Sample Input 3

1
200 1

Sample Output 3

148322100

 Note that the value modulo 1000000007 ( 10^9 + 7 ) must be printed. 

 This case satisfies the constraint of the partial score. 



Sample input:
2
20 8
20 12


Sample output:
24
20

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

def precompute(M):
    # 残り M 秒あるとする。
    # dp1：人数
    # dp2：生産開始時刻の総和
    g = M + 10
    dp1 = np.ones(M, np.int64)
    dp2 = np.zeros(M, np.int64)
    while g * (g - 1) // 2 > M:
        g -= 1
    while g >= 1:
        newdp1 = np.ones_like(dp1)
        newdp2 = np.zeros_like(dp2)
        for m in range(2 * g, M):
            newdp1[m] = (newdp1[m - g] + dp1[m - g]) % MOD
            newdp2[m] = (newdp2[m - g] + dp2[m - g] + g * newdp1[m]) % MOD
        g -= 1
        dp1, dp2 = newdp1, newdp2
    return dp1, dp2

def main(NC):
    dp1, dp2 = precompute(100_010)
    N, C = NC[::2], NC[1::2]
    for i in range(len(N)):
        n, c = N[i], C[i]
        q, r = divmod(n, c)
        ans = dp1[q] * n - dp2[q] * c
        print(ans % MOD)

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    precompute = cc_export(precompute, (i8, ))
    main = cc_export(main, (i8[:], ))
    cc.compile()

from my_module import main

NC = np.array(read().split(), np.int64)[1:]

main(NC)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

@njit((i8, ), cache=True)
def precompute(M):
    # 残り M 秒あるとする。
    # dp1：人数
    # dp2：生産開始時刻の総和
    g = M + 10
    dp1 = np.ones(M, np.int64)
    dp2 = np.zeros(M, np.int64)
    while g * (g - 1) // 2 > M:
        g -= 1
    while g >= 1:
        newdp1 = np.ones_like(dp1)
        newdp2 = np.zeros_like(dp2)
        for m in range(2 * g, M):
            newdp1[m] = (newdp1[m - g] + dp1[m - g]) % MOD
            newdp2[m] = (newdp2[m - g] + dp2[m - g] + g * newdp1[m]) % MOD
        g -= 1
        dp1, dp2 = newdp1, newdp2
    return dp1, dp2

@njit((i8[:], ), cache=True)
def main(NC):
    dp1, dp2 = precompute(100_010)
    N, C = NC[::2], NC[1::2]
    for i in range(len(N)):
        n, c = N[i], C[i]
        q, r = divmod(n, c)
        ans = dp1[q] * n - dp2[q] * c
        print(ans % MOD)

NC = np.array(read().split(), np.int64)[1:]

main(NC)