Possible number of Trees having N vertex | Python3 program for the above approach ; Function that finds the value of x ^ y using Modular Exponentiation ; Base Case ; If y is odd , multiply x with result ; Return the value ; Function that counts the total number of trees possible ; Find the max element in array ; Level array store the number nodes on level i initially all values are 0 ; In this case tree can not be created ; Calculate level [ i ] ^ level [ i + 1 ] ; Return the final count ; Driver Code ; Given Queries ; Function call
mod = int ( 1e9 + 7 ) NEW_LINE def power ( x , y ) : NEW_LINE INDENT if ( y == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT p = power ( x , y // 2 ) % mod NEW_LINE p = ( p * p ) % mod NEW_LINE if ( y & 1 ) : NEW_LINE INDENT p = ( x * p ) % mod NEW_LINE DEDENT return p NEW_LINE DEDENT def NumberOfTrees ( arr , N ) : NEW_LINE INDENT maxElement = max ( arr ) NEW_LINE level = [ 0 ] * ( maxElement + 1 ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT level [ arr [ i ] ] += 1 NEW_LINE DEDENT if ( arr [ 0 ] != 0 or level [ 0 ] != 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT ans = 1 NEW_LINE for i in range ( maxElement ) : NEW_LINE INDENT ans = ( ans * power ( level [ i ] , level [ i + 1 ] ) ) % mod NEW_LINE DEDENT return ans NEW_LINE DEDENT N = 7 NEW_LINE arr = [ 0 , 3 , 2 , 1 , 2 , 2 , 1 ] NEW_LINE print ( NumberOfTrees ( arr , N ) ) NEW_LINE