KLVASCIS - Salama’s Birthday

no tags 

It's a wonderful day, today is Salama's 20th birthday.

Being joyful and triumphant, every year he gains the love of the people. He noticed that each year the number of friends ti he makes increases by a factor r, while in his first year he made a friends. (a = r-1)

The number of friends he makes in the ith year is a ri-1.

It's commonly known that Salama loves math. Help him calculate Sn (the number of friends he will make in his first n years) modulo 1000003 (106 + 3).

Sn = a + a r + a r2 + a r3 + .... + a rn-1

Note:
X modulo Y (X%Y) is the remainder of dividing X by Y. 

Input

Your program will be tested on one or more test cases. The first line of input will be a single integer T,
The number of test cases (1<=T<=20).Followed by T lines, each line consists of three integers a, r and n.
a = r-1
1 < r < 10
0 < n < 106 (May he live long and happily!)

Output

For each test case, print “Case_#i:_X” where “X” is your answer modulo 1000003(106 +3), “i” is the number of the test case (starting with 1) and “_” is a white space. Each output should be printed in a separate line.

Example

Input:
3
1 2 1
8 9 3
2 3 2 Output:
Case #1: 1
Case #2: 728
Case #3: 8


Added by:Mohamed Ali
Date:2014-01-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:acmASCIS Level 1 Contest 2014