# PROBLEM LINK:

**Author:** Abhijeet Jha

**Tester:** Aswin Ashok

**Editorialist:** Aswin Ashok

# DIFFICULTY:

EASY

# PREREQUISITES:

Math, Modular Arithmetic

# PROBLEM:

Find \sum_{i=1}^{n}\prod_{k=1}^{t}(i+k). Print the sum \mod 10^9+7.

# QUICK EXPLANATION:

The final answer is t!*(^{n+t+1}C_{t+1}-1)

# EXPLANATION:

Let us take the given example and try to reduce it to a general formula.

In the Given Sample Case **n=3 t=2**.

Therefore sum = 2*3 + 3*4 + 4*5

Notice that:

1*2=\frac{2!}{0!}

2*3=\frac{3!}{1!}

3*4=\frac{4!}{2!}

4*5=\frac{5!}{3!}

So each term is of the form \frac{x!}{(x-t)!}

If we multiply and divide by t! it becomes t!*\frac{x!}{(x-t)!t!}

Which is nothing but t!* ^xC_t

Therefore sum = t!*\sum_{x=t+1}^{n+t}\ ^xC_t

But we know \sum_{x=t}^{N}\ ^xC_t = ^{N+1}C_{t+1}

Therefore \sum_{x=t+1}^{n+t}\ ^xC_k =^{n+t+1}C_{t+1} - 1

So final expression comes out to be t!* ^{n+t+1}C_{t+1} -t!

But since n is so large we can not calculate it directly, we have to Simplify the above expression.

On Simplifying we get \frac{\prod_{i=1}^{t+1} (n+i)}{t+1}-t!

# TIME COMPLEXITY

For each test case the final simplified expression can be evaluated in O(t) and there are **Q** test cases so overall complexity is O(Q*t)

# AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.