Find the sum of the costs of all possible arrangements of the cells | Python3 implementation of the approach ; To store the factorials and factorial mod inverse of the numbers ; Function to return ( a ^ m1 ) % mod ; Function to find the factorials of all the numbers ; Function to find factorial mod inverse of all the numbers ; Function to return nCr ; Function to return the sum of the costs of all the possible arrangements of the cells ; For all possible X 's ; For all possible Y 's ; Driver code
N = 100005 NEW_LINE mod = ( int ) ( 1e9 + 7 ) NEW_LINE factorial = [ 0 ] * N ; NEW_LINE modinverse = [ 0 ] * N ; NEW_LINE def power ( a , m1 ) : NEW_LINE INDENT if ( m1 == 0 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT elif ( m1 == 1 ) : NEW_LINE INDENT return a ; NEW_LINE DEDENT elif ( m1 == 2 ) : NEW_LINE INDENT return ( a * a ) % mod ; NEW_LINE DEDENT elif ( m1 & 1 ) : NEW_LINE INDENT return ( a * power ( power ( a , m1 // 2 ) , 2 ) ) % mod ; NEW_LINE DEDENT else : NEW_LINE INDENT return power ( power ( a , m1 // 2 ) , 2 ) % mod ; NEW_LINE DEDENT DEDENT def factorialfun ( ) : NEW_LINE INDENT factorial [ 0 ] = 1 ; NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT factorial [ i ] = ( factorial [ i - 1 ] * i ) % mod ; NEW_LINE DEDENT DEDENT def modinversefun ( ) : NEW_LINE INDENT modinverse [ N - 1 ] = power ( factorial [ N - 1 ] , mod - 2 ) % mod ; NEW_LINE for i in range ( N - 2 , - 1 , - 1 ) : NEW_LINE INDENT modinverse [ i ] = ( modinverse [ i + 1 ] * ( i + 1 ) ) % mod ; NEW_LINE DEDENT DEDENT def binomial ( n , r ) : NEW_LINE INDENT if ( r > n ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT a = ( factorial [ n ] * modinverse [ n - r ] ) % mod ; NEW_LINE a = ( a * modinverse [ r ] ) % mod ; NEW_LINE return a ; NEW_LINE DEDENT def arrange ( n , m , k ) : NEW_LINE INDENT factorialfun ( ) ; NEW_LINE modinversefun ( ) ; NEW_LINE ans = 0 ; NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT ans += ( i * ( n - i ) * m * m ) % mod ; NEW_LINE DEDENT for i in range ( 1 , m ) : NEW_LINE INDENT ans += ( i * ( m - i ) * n * n ) % mod ; NEW_LINE DEDENT ans = ( ans * binomial ( n * m - 2 , k - 2 ) ) % mod ; NEW_LINE return int ( ans ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 2 ; m = 2 ; k = 2 ; NEW_LINE print ( arrange ( n , m , k ) ) ; NEW_LINE DEDENT