Chocolate or Money

Input: Standard Input

Output: Standard Output

Nowadays it is a trend to give one chocolate instead of 1 taka (currency of Bangladesh) and even two chocolates instead of 2 taka. Though both kids and shopkeeper may be happy with these, but not everyone. I was thinking what if we buy a packet of 50 chocolates by 40 taka and use these instead of money. May be while buying a car instead of giving a check of 1,000,000 taka we can give 20,000 packets of chocolates (and thus saving 200,000 taka)!! How weird thinking! But then I thought if one does not have 1 taka coin then yes one chocolate can save my day! But do we need chocolate always? Or better to ask, if we don’t have chocolate then can other items save our day? Let’s go and check it.

Instead of using chocolates, let's say there are N types of items that can be exchanged. Suppose P(x) = number of ways a subset of the given items can be chosen so that if the buyer and the seller both have sufficient number of these items (in subset) they can exchange x taka.

For example, there are three items, X, Y and Z and their prices are 2, 4, and 2 taka respectively. Then P(1) = 0, P(2) = 6 (X, Z, ZY, XZ, YZ, XYZ), P(3) = 0, P(4) = 7 (X, Y, Z, XY, YZ, XZ, XYZ).

And you will also be given an integer C, you have to find P(1) + ... + P(C) or . So, if C = 4, then for the above case, the result is 0 + 6 + 0 + 7 = 13.

However, it is not always possible to have N items in a shop right? So we are also interested to find out the sum if we give restriction that there is exactly K items in the shop (instead of any item). That is, the size of the subset is exactly K. Say for K = 2, for the above case, P(1) = 0, P(2) = 3 (XY, YZ,
ZX), P(3) = 0, P(4) = 3 (XY, YZ, ZX). So answer is: 6.

Input

In the input file, first line contains number of test cases, T (T ≤ 40). Hence followed by three positive numbers N, C and K. (N ≤ 10⁵, C ≤ 10¹⁵, K ≤ N). In the next line, there are 3 integers a, b and c (0 < a, b, c ≤ 10⁵). With the help of these 3 integers you can generate the price of all N things. It can be generated as follows:

Price[0] = a

Price[1] = b

Price[i] = 1 + (a*Price[i-2] + b*Price[i-1] + c)%100000 (for 2 ≤ i < N)

Output

For each case, output the number of test case and then the required solutions, first one is any size subset and second one is for K size subset. Since the answers can be very big print them in modulo 1,000,000,007. For details please follow the sample input output.

Sample Input Output for Sample Input

3 4 2

2 4 2

Case 1: 17 10

Problemsetter: Md. Mahbubul Hasan, Special Thanks: Hasnain Heickal, Jane Alam Jan