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}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def modifiedSum(self, N, M, K):
        #code here

Solutions:
class Solution:

	def modifiedSum(self, N, M, K):

		def sum(n):
			return n * (n + 1) % 1000000007
		for i in range(1, M + 1):
			N = sum(K + N)
		return N


class Solution:

	def modifiedSum(self, N, M, K):
		ans = 0
		mod = int(1000000000.0 + 7)
		for i in range(M):
			temp = N + K
			ans = temp * (temp + 1)
			ans %= mod
			N = ans


class Solution:

	def summ(self, n):
		return n * (n + 1) % 1000000007

	def modifiedSum(self, N, M, K):
		ans = 0
		a = N + K
		for i in range(1, M + 1):
			ans = self.summ(a)
			a = ans + K
		return ans


class Solution:

	def modifiedSum(self, N, M, K):
		while M:
			N = (N + K) * (N + K + 1) % (10 ** 9 + 7)
			M -= 1
		return N


class Solution:

	def modifiedSum(self, n, m, k):
		p = n
		for i in range(m):
			p = k + p
			p = p * (p + 1)
			p = p % 1000000007
		return p % 1000000007