maksyuki 发表于 oj 分类,标签:

1325 - Distributing Chocolates

InputNow as the result can be large, I asked for the result modulo 100 000 007 (a prime). But after that I found that this problem is easier than I thought. So, I changed the problem a little bit. I will give you the number of my cousins K and the result modulo 100 000 007. Your task is to find the number of chocolates I have bought. If there are several solutions, you have to find the minimum one.I have bought n chocolates for my young cousins. Every chocolate is different. So, in the contest I added the problem that how many ways I can distribute the chocolates to my K cousins. I can give more chocolates to some cousins, and may give no chocolate to some. For example, I have three cousins and I bought 2 chocolates a and b. Then I can distribute them in the following 9 ways:

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers K (2 ≤ K ≤ 107and result (0 ≤ result < 100000007). You can assume that the input data is valid, that means a solution exists.


For each case, print the case number and the minimum possible number of chocolates I have bought.

Sample Input

Output for Sample Input

23 92 100 Case 1: 2Case 2: 23502611