MODULO 10^9 + 7 output.
The modulo operation is the same as the remainder of the division . a modulo b is c , means that the remainder when a is divided by b is c.It is represented by the ‘%’ operator in many programming languages. For eg: 5%2=1 What is the necessary of MODULO 10^9+7 : The largest integer data type in C/C++ is the long long int ; its size is 64 bits and can store integers from ( –2^63 ) to ( +2^63 -1 ) . Integers as large as 9 X 10^18 can be stored in a long long int . But in problems like calculating the number of permutations of a size n array, even this large range may prove insufficient. We know that the number of permutations of a size n array is n! . Even for a small value of n, the answer can be very large. Eg, for n=21, the answer is 21! which is about 5 x 10^19 and too large for a long long int variable to store. This makes calculating values of large factorials difficult. So, instead of asking th...