static long factorial(int n)
{
long M = 1000000007;
long f = 1;
for (int i = 1; i <= n; i++)
f = (f*i) % M; // Now f never can
// exceed 10^9+7
return f;
}
// This code is contributed by Dharanendra L V.