Given two numbers N and T where, 
and 
. The task is to find the value of 
.
Since sum can be large, output it modulo 109+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)%pll 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 answerll 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 seriespublic 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)%pdef 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 answerdef 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 Codeif __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 seriesusing System;class GFG {static long MOD = 1000000007;// function to calculate (a^b)%pstatic 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 answerstatic long sumProd(long n, long t){ // modulo inverse of denominatorlong dino = power(t + 1, MOD - 2, MOD);// calculating commentator partlong 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 answerans = ans * dino - tfact + MOD;return ans % MOD;}// Driver Codepublic 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)%pfunction 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 answerfunction 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 sumecho sumProd($n, $t);// This code is contributed// by Shivi_Aggarwal?> |
Javascript
<script>// Javascript program to find sum of product // of number in given seriesvar MOD = 100000007;// function to calculate (a^b)%pfunction 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 answerfunction 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 sumdocument.write( sumProd(n, t));// This code is contributed by noob2000.</script> |
Output:
38
Time Complexity: O(n+t)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
