Count the number of ways to fill K boxes with N distinct items | Java program to calculate the above formula ; To store the factorials of all numbers ; Function to calculate factorial of all numbers ; Calculate x to the power y in O ( log n ) time ; Function to find inverse mod of a number x ; Calculate ( n C r ) ; Loop to compute the formula evaluated ; Add even power terms ; Subtract odd power terms ; Choose the k boxes which were used ; Driver Code
import java . util . * ; class GFG { static long mod = 1000000007 ; static long factorial [ ] = new long [ 100005 ] ; static void StoreFactorials ( int n ) { factorial [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { factorial [ i ] = ( i * factorial [ i - 1 ] ) % mod ; } } static long Power ( long x , long y ) { long ans = 1 ; while ( y > 0 ) { if ( y % 2 == 1 ) { ans = ( ans * x ) % mod ; } x = ( x * x ) % mod ; y /= 2 ; } return ans ; } static long invmod ( long x ) { return Power ( x , mod - 2 ) ; } static long nCr ( int n , int r ) { return ( factorial [ n ] * invmod ( ( factorial [ r ] * factorial [ n - r ] ) % mod ) ) % mod ; } static long CountWays ( int n , int k ) { StoreFactorials ( n ) ; long ans = 0 ; for ( int i = k ; i >= 0 ; i -- ) { if ( i % 2 == k % 2 ) { ans = ( ans + ( Power ( i , n ) * nCr ( k , i ) ) % mod ) % mod ; } else { ans = ( ans + mod - ( Power ( i , n ) * nCr ( k , i ) ) % mod ) % mod ; } } ans = ( ans * nCr ( n , k ) ) % mod ; return ans ; } public static void main ( String [ ] args ) { int N = 5 ; int K = 5 ; System . out . print ( CountWays ( N , K ) + "NEW_LINE"); } }