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.

Problem statement:

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 â€¦??