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;
}