What is Find sum of product of number in given series?

In this article, we will learn Find sum of product of number in given series,This free Data Structures and Algorithms tutorial for complete beginners will help you learn Data Structures and Algorithms from scratch.

Find sum of product of number in given series️‍🔥

Given two numbers N and T where, and . The task is to find the value of .
Since sum can be large, output it modulo 10⁹+7.
Examples:

Input : 3 2
Output : 38
2*3 + 3*4 + 4*5 = 38

Input : 4 2
Output : 68

In the Given Sample Case n = 3 and t = 2.
sum = 2*3+3*4+4*5.
Notice that:

So each term is of the form
If we multiply and divide by t! it becomes
Which is nothing but
Therefore,
But we know
Therefore
So final expression comes out to be
But since n is so large we can not calculate it directly, we have to Simplify the above expression.
On Simplifying we get  .
Below is the implementation of above approach

C++

// C++ program to find sum of product 
// of number in given series
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const long long MOD = 1000000007;
 
// function to calculate (a^b)%p
ll power(ll x, unsigned long long y, ll p)
{
    ll res = 1; // Initialize result
 
    // Update x if it is more than or equal to p
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
 
    return res;
}
 
// function to return required answer
ll sumProd(ll n, ll t)
{
    // modulo inverse of denominator
    ll dino = power(t + 1, MOD - 2, MOD);
 
    // calculating commentator part
    unsigned long long ans = 1;
    for (ll i = n + t + 1; i > n; --i)
        ans = (ans % MOD * i % MOD) % MOD;
 
    // calculating t!
    ll tfact = 1;
    for (int i = 1; i <= t; ++i)
        tfact = (tfact * i) % MOD;
 
    // accumulating the final answer
    ans = ans * dino - tfact + MOD;
 
    return ans % MOD;
}
int main()
{
    ll n = 3, t = 2;
 
    // function call to print required sum
    cout << sumProd(n, t);
 
    return 0;
}

Java

// Java program to find sum of product 
// of number in given series
 
public class GFG {
 
     static long MOD = 1000000007;
      
    //function to calculate (a^b)%p
     static long power(long x, long y, long p)
     {
      long res = 1; // Initialize result
 
      // Update x if it is more than or equal to p
      x = x % p;
 
      while (y > 0) {
 
          // If y is odd, multiply x with result
          if ((y & 1)!= 0)
              res = (res * x) % p;
 
          // y must be even now
          y = y >> 1; // y = y/2
          x = (x * x) % p;
      }
 
      return res;
     }
 
     //function to return required answer
     static long sumProd(long n, long t)
     {
      // modulo inverse of denominator
      long dino = power(t + 1, MOD - 2, MOD);
 
      // calculating commentator part
      long ans = 1;
      for (long i = n + t + 1; i > n; --i)
          ans = (ans % MOD * i % MOD) % MOD;
 
      // calculating t!
      long tfact = 1;
      for (int i = 1; i <= t; ++i)
          tfact = (tfact * i) % MOD;
 
      // accumulating the final answer
      ans = ans * dino - tfact + MOD;
 
      return ans % MOD;
     }
 
     // Driver program
    public static void main(String[] args) {
         
        long n = 3, t = 2;
 
         // function call to print required sum
         System.out.println(sumProd(n, t));
    }
}

Python3

# Python 3 program to find sum of product 
# of number in given series 
 
MOD = 1000000007
 
# function to calculate (a^b)%p
def power(x, y, p) :
 
    # Initialize result
    res = 1
 
    # Update x if it is more than or equal to p
    x = x % p
 
    # If y is odd, multiply x with result 
    while y > 0 :
 
        if y & 1 :
            res = (res * x) % p
 
        #  y must be even now
        y = y >> 1 # y = y/2
        x = (x * x) % p
 
    return res
 
# function to return required answer
def sumProd(n, t) :
 
    # modulo inverse of denominator 
    dino = power(t + 1, MOD - 2, MOD)
 
    ans = 1
 
    # calculating commentator part 
    for i in range(n + t + 1 , n, -1) :
        ans = (ans % MOD * i % MOD) % MOD
 
    # calculating t! 
    tfact = 1
    for i in range(1, t+1) :
        tfact = (tfact * i) % MOD
 
    # accumulating the final answer 
    ans = ans * dino - tfact + MOD
 
    return ans % MOD
             
     
# Driver Code
if __name__ == "__main__" :
 
    n, t = 3, 2
 
    # function call to print required sum 
    print(sumProd(n, t))
 
# This code is contributed by ANKITRAI1

C#

// C# program to find sum of product 
// of number in given series
using System;
class GFG 
{
static long MOD = 1000000007;
 
// function to calculate (a^b)%p
static long power(long x, long y, 
                  long p)
{
    long res = 1; // Initialize result
     
    // Update x if it is more
    // than or equal to p
    x = x % p;
     
    while (y > 0) 
    {
     
        // If y is odd, multiply x 
        // with result
        if ((y & 1) != 0)
            res = (res * x) % p;
     
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
 
    return res;
}
 
// function to return required answer
static long sumProd(long n, long t)
{
     
// modulo inverse of denominator
long dino = power(t + 1, MOD - 2, MOD);
 
// calculating commentator part
long ans = 1;
for (long i = n + t + 1; i > n; --i)
    ans = (ans % MOD * i % MOD) % MOD;
 
// calculating t!
long tfact = 1;
for (int i = 1; i <= t; ++i)
    tfact = (tfact * i) % MOD;
 
// accumulating the final answer
ans = ans * dino - tfact + MOD;
 
return ans % MOD;
}
 
// Driver Code
public static void Main() 
{
    long n = 3, t = 2;
 
    // function call to print required sum
    Console.WriteLine(sumProd(n, t));
}
}
 
// This code is contributed 
// by Akanksha Rai(Abby_akku)

PHP

<?php
// PHP program to find sum of product 
// of number in given series
 
// function to calculate (a^b)%p
function power($x, $y, $p)
{
    $res = 1; // Initialize result
 
    // Update x if it is more 
    // than or equal to p
    $x = $x % $p;
 
    while ($y > 0) 
    {
 
        // If y is odd, multiply 
        // x with result
        if ($y & 1)
            $res = ($res * $x) % $p;
 
        // y must be even now
        $y = $y >> 1; // y = y/2
        $x = ($x * $x) % $p;
    }
 
    return $res;
}
 
// function to return required answer
function sumProd($n, $t)
{
    $MOD = 1000000007;
     
    // modulo inverse of denominator
    $dino = power($t + 1, $MOD - 2, $MOD);
 
    // calculating commentator part
    $ans = 1;
    for ($i = $n + $t + 1; $i > $n; --$i)
        $ans = ($ans % $MOD * $i % 
                       $MOD) % $MOD;
 
    // calculating t!
    $tfact = 1;
    for ($i = 1; $i <= $t; ++$i)
        $tfact = ($tfact * $i) % $MOD;
 
    // accumulating the final answer
    $ans = $ans * $dino - $tfact + $MOD;
 
    return $ans % $MOD;
}
 
// Driver code
$n = 3;
$t = 2;
 
// function call to print
// required sum
echo sumProd($n, $t);
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
 
 
// Javascript program to find sum of product 
// of number in given series
var MOD = 100000007;
 
// function to calculate (a^b)%p
function power(x, y, p)
{
    var res = 1; // Initialize result
 
    // Update x if it is more than or equal to p
    x = x % p;
 
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
 
    return res;
}
 
// function to return required answer
function sumProd(n, t)
{
    // modulo inverse of denominator
    var dino = power(t + 1, MOD - 2, MOD);
 
    // calculating commentator part
    var ans = 1;
    for (var i = n + t + 1; i > n; --i)
        ans = (ans % MOD * i % MOD) % MOD;
 
    // calculating t!
    var tfact = 1;
    for (var i = 1; i <= t; ++i)
        tfact = (tfact * i) % MOD;
 
    // accumulating the final answer
    ans = ans * dino - tfact + MOD;
 
    return ans % MOD;
}
 
 
var n = 3, t = 2;
// function call to print required sum
document.write( sumProd(n, t));
 
// This code is contributed by noob2000.
</script>

Output:

Time Complexity: O(n+t)

Auxiliary Space: O(1)