There was problem given to be in a hiring challenge which i was not able to solve completely so i am just curious to know what i missed.
Given a number of vertices (n), determine the number of ways these vertices can form a graph, the graph can be disjoint so it is not necessary to connect all vertices. The answer can be very large so return modulo 10^9+7 ;
Constrains: 1 < n < 10^9
What i did is used the formula 2^(n*(n-1)/2) to get number of all possible graphs and used modular exponentiation to compute value, but i was not able to pass all test cases.
Can anyone tell me what i did wrong or is it some other concept to be used …??