Summing the sum

Problem

Ishaan was playing with numbers. He knew how to calculate the sum of numbers. He defined a function for his use which calculates the twice sum of first N natural numbers as sum(N).

But being curious, he modified his function to calculate something more complex. He defined his function to be sumX(N,M,K).

Now this function calculates :

sum( K + sum( K + sum( K + ...sum(K + N)...))) , continuing for M terms (Refer example for explanation).

Given N, M and K, calculate the value of sumX(N,M,K).

Input

First line of input contains a single integer T denoting the number of test cases.

The only line of each test case contains 3 space-separated integers N, M and K.

Output

For each test case, print the required answer in a new line.

Constraints

1 <= T <= 200

1 <= N <= 1000

1 <= M <= 1000

1 <= K <= 1000

Input

3

1 2 3

2 2 2

3 3 2

Output

552

506

1120422

Explanation

Case 1 : 

sum(3 + sum(3 + 1) ) = sum(3 + 20) = 552

Case 2 : 

sum(2 + sum(2 + 2) ) = sum(2 + 20) = 506

Case 3 : 

sum(2 + sum(2 + sum(2 + 3) ) ) = sum(2 + sum( 2 + 30 ) ) = sum(2 + 1056) = 1120422

Solution

The programming solution can get tricky, specially when using dynamic programming to solve. First we need the basic sum function that Ishaan had created

// to store all the summations calculated
private static int[] dp = new int[10000];

private static int sum(int x) {
    if (dp[x] != 0) {
        // already calculated
        return dp[x];
    } else if (x == 0 || x == 1) {
        return x;
    } else {
        // summation from x down to 0
        dp[x] = x + sum(x - 1);
        return dp[x];
    }
}

The array dp is used to store calculations that have already been made (to save time). The new sumX function calculates sum( K + sum( K + sum( K + ...sum(K + N)...))), for M terms. A bottom up procedure seems easiest, as the formula shows that the last calculation needed is sum(K+N) and it doesn't depend on another result. Therefore, doing this recursively becomes easier, as the base case is simple, and the sumX calculations can be reflected into programming easily

private static int sumX(int N, int M, int K) {
    if (M == 1) {
        // last calculation is just the summation of N + K
        return 2 * sum(N + K);
    } else {
        // recursively calculate the summation of K + sumX(K + ...) M times
        return 2 * sum(K + sumX(N, M - 1, K));
    }
}

And lastly, just call the sumX function with the data read in from the file that has similar data to

3

1 2 3

2 2 2

3 3 2

public static void main(String[] args) {
    try {
        // read in the data from file
        Scanner scanner = new Scanner(new File("input.txt"));
        int T = scanner.nextInt();
        for (int x = 0; x < T; x++) {
            int N = scanner.nextInt();
            int M = scanner.nextInt();
            int K = scanner.nextInt();
            // calculate and print answer
            System.out.println(sumX(N, M, K));
        }
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }
}

Credit to geeksforgeeks for the question.