Given three integers N, M, and K. Lets Sum(N) be a function that calculates twice the sum of first N natural numbers. Calculate Sum(K+Sum(K+Sum(K+....+Sum(N+K) up to M terms.
Example 1:
Input:
N=1, M=2, K=3
Output:
552
Explanation:
Sum(3+Sum(3+1))=Sum(3+Sum(4))
=Sum(3+20)=Sum(23)=Sum(552)
Example 2:
Input:
N=2, M=2, K=2
Output:
506
Explanation:
Sum(2+Sum(2+2))=Sum(2+Sum(4))
Sum(2+20)=506
Your Task:
You don't need to read input or print anything. Your task is to complete the function modifiedSum() which takes three integers N, M, and K as input parameters and returns the required sum.
Note: Since the answer can be very large, return the answer modulo 10^9 + 7.
Expected Time Complexity:O(M)
Expected Auxillary Space:O(1)
Constraints:
1<=N,M,K<=10^{6}

见题面

见题面