To store the factorial and factorial mod inverse of the numbers
static long [ ] factorial = new long [ 1000005 ] ; static long [ ] modinverse = new long [ 1000005 ] ; static long mod = 1000000007 ; static int N = 1000005 ;