Ishtiaque and the Rabbit

Mr Ishtiaque is in trouble. A few months ago, he bought 2 rabbits. He wanted to have two pet rabbits. But he did not know that rabbits reproduce so fast. Now, his little balcony has been filled up with rabbits. So he decided to build a big house for his pets. But he needs an estimation about how many rabbits will be there by the end of the year. As he is a teacher and moreover he has to take care of his rabbits every day, he does not have much time to make the estimation. So he needs your help regarding this issue. He will provide some information about the rabbits.

For example, at first he had 2 rabbits. Then after the end of first month he had 6 more rabbits. After the second month, he had 18 more rabbits. That means the count of new rabbits gets tripled every month. So you have to find out how many rabbits will be in total up to a given month.

Input

First line of the input contains an integer $T$ ($1 < T < 1000$) which denotes the number of test cases. Next T line contains three integers $A$ ($1 < A < 1000000000$) which denotes the number of rabbits in the first month, $R$ ($1 < R < 1000000000$) that denotes the common ratio of the rabbits between the two consecutive months and $N$ ($1 < N < 1000000000$), the month until which you will calculate the sum of the rabbits from first month.

Output

For each input, output the total sum of rabbits from first to the start of nth month. Since the result can be very large, print the result modulo 1000003.

Sample

Input	Output
2 2 3 2 2 3 3	8 26