Jack And Rum
All submissions for this problem are available.
Jack Sparrow, sorry Captain Jack Sparrow, is out of rum. He needs to send some of his crew members to rob Tortuga's rum deposits. Tortuga's rum deposits have infinite number of bottles and each of them is labelled uniquely by a bottle_id as an integer starting from 0, ranging ofcourse till infinity without any missing integer. The infinite resource of these bottles must be well secured by Tortuga. As a result, P bottles having continuous numbers are grouped into one secure base. Thus, first P bottles starting from bottle_id 0 are secured in the first base, then next P bottles in next base and so on till infinity. Tortuga's people are attracted to prime numbers, thus P is always chosen to be a prime. The secure bases are identified with a special base_id defined by the minimum bottle_id of all the bottles present in the base. The base_id for each base also stores a special information about that base for the administration of Tortuga. It secretly represents the number of security gates that the particular base have as protection from robbery.
Jack being a brilliant captain came up with an ingenious plan to rob Tortuga. He analysed the complete distribution of rum bottles and the amount of security associated with each base. He decided that the robbery will be done in N phases and apparently there are exactly N persons in Jack's crew excluding Jack. Jack, being coward, never goes for a robbery.
In each phase, Jack selects a secure base as target of rum and tries to rob it. In the ith (1 <= i <= N) phase, Jack will make a group of size i from the crew, and send the group to rob the selected base. After these crew members return, again a group of size i is formed from the crew and sent to the same base, and so forth. Each such group must have at least one different member when compared from all the groups previously sent in this phase. Simply saying, the exact same group of people can never be sent twice in one phase. Observe carefully that though each crew member can be sent many times as part of different groups, but the group as a whole can be sent only once. The phase continues until there are no possible distinct group of size i that could be formed out of the crew.
Each group sent performs a particular task. They must break exactly one gate of the target base chosen for that robbery phase. Thus, a phase is successful if and only if the total number of groups sent in that phase is exactly equal to the number of gates of the target secure base. In all other cases, the phase is a failure implying that no rum is robbed and all the security gates of the selected base are restored making them again equal to their base_id. In the case of a successful robbery, the members bring back all the rum bottles present in that base. Once, a particular base has been robbed successfully, the security men of Tortuga captures the base and no further attempt can be made on that base in any of the succeeding phases.
As an admirer of Jack, you need to output the number of rum bottles that jack will get at the end of the whole robbery, assuming that Jack plans all the phases optimally maximizing the number of bottles he can rob. Since the number of bottles can be huge, you need to output the answer modulo 1,000,000,007.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case contains only one line having two integers, P and N.
For each test case, output a single integer representing the number of rum bottles that Jack successfully robbed modulo 1,000,000,007.
- 1 <= T <= 100000
- 1 <= N <= 1018
- 1 <= P <= 109
- P will be a prime number.
Input 2 2 2 3 2
Output 2 0
|Time Limit:||3.63636 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.