Product of first N factorials in C++

Given a number N, the task is to find the product of first N factorials modulo by 1000000007. . Factorial implies when we find the product of all the numbers below that number including that number and is denoted by ! (Exclamation sign), For example − 4! = 4x3x2x1 = 24.

So, we have to find a product of n factorials and modulo by 1000000007..

Constraint 

1 ≤ N ≤ 1e6.

Input 

n = 9

Output 

27

Explanation 

1! * 2! * 3! * 4! * 5! * 6! * 7! * 8! * 9! Mod (1e9 + 7) = 27

Input 

n = 3

Output 

12

Explanation 

1! * 2! * 3! mod (1e9 +7) = 12

Approach used below is as follows to solve the problem

• Find the factorial recursively from i = 1 till n and product all the factorials

• Mod the product of all the factorials by 1e9 +7

• Return the result.

Algorithm

In Fucntion long long int mulmod(long long int x, long long int y, long long int mod) Step 1→ Declare and Initialize result as 0 Step 2→ Set x as x % mod Step 3→ While y > 0    If y % 2 == 1 then,       Set result as (result + x) % mod    Set x as (x * 2) % mod    Set y as y/ 2 Step 4→ return (result % mod) In Function long long int nfactprod(long long int num)    Step 1→ Declare and Initialize product with 1 and fact with 1    Step 2→ Declare and Initialize MOD as (1e9 + 7)    Step 3→ For i = 1 and i <= num and i++       Set fact as (call function mulmod(fact, i, MOD))       Set product as (call function mulmod(product, fact, MOD))       If product == 0 then,          Return 0    Step 4→ Return product In Function int main()    Step 1→ Declare and Initialize num = 3    Step 2→ Print the result by calling (nfactprod(num)) Stop

Example

 Live Demo

#include <stdio.h> long long int mulmod(long long int x, long long int y, long long int mod){    long long int result = 0;    x = x % mod;    while (y > 0) {       // add x where y is odd.       if (y % 2 == 1)          result = (result + x) % mod;       // Multiply x with 2       x = (x * 2) % mod;       // Divide y by 2       y /= 2;    }    return result % mod; } long long int nfactprod(long long int num){    // Initialize product and fact with 1    long long int product = 1, fact = 1;    long long int MOD = 1e9 + 7;    for (int i = 1; i <= num; i++) {       // to find factorial for every iteration       fact = mulmod(fact, i, MOD);       // product of first i factorials       product = mulmod(product, fact, MOD);       //when product divisible by MOD return 0       if (product == 0)          return 0;    }    return product; } int main(){    long long int num = 3;    printf("%lld \n", (nfactprod(num)));    return 0; }

Output

If run the above code it will generate the following output −

12