# Count of distinct graphs that can be formed with N vertices

Given an integer **N** which is the number of vertices. The task is to find the number of distinct graphs that can be formed. Since the answer can be very large, print the **answer % 1000000007**.**Examples:**

Input:N = 3Output:8Input:N = 4Output:64

**Approach:**

- The maximum number of edges a graph with
**N**vertices can contain is**X = N * (N – 1) / 2.** - The total number of graphs containing
**0**edge and**N**vertices will be^{X}C_{0} - The total number of graphs containing
**1**edge and**N**vertices will be^{X}C_{1} - And so on from a number of edges 1 to
**X**with**N**vertices - Hence, the total number of graphs that can be formed with n vertices will be:
^{X}C_{0}+^{X}C_{1}+^{X}C_{2}+ … +^{X}C_{X}= 2^{X}.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `const` `int` `MOD = 1e9 + 7;` `// Function to return (x^y) % MOD` `// in O(log(y))` `long` `long` `power(` `long` `long` `x,` ` ` `long` `long` `y,` ` ` `const` `int` `& MOD)` `{` ` ` `long` `long` `res = 1;` ` ` `while` `(y > 0) {` ` ` `if` `(y & 1)` ` ` `res = (res * x) % MOD;` ` ` `x = (x * x) % MOD;` ` ` `y /= 2;` ` ` `}` ` ` `return` `res;` `}` `// Function to return the count of distinct` `// graphs possible with n vertices` `long` `long` `countGraphs(` `int` `n)` `{` ` ` `// Maximum number of edges for a` ` ` `// graph with n vertices` ` ` `long` `long` `x = n * (n - 1) / 2;` ` ` `// Function to calculate` ` ` `// (2^x) % mod` ` ` `return` `power(2, x, MOD);` `}` `// Driver code` `int` `main()` `{` ` ` `int` `n = 5;` ` ` `cout << countGraphs(n);` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the approach` `class` `GFG` `{` ` ` `static` `final` `int` `MOD = (` `int` `)1e9 + ` `7` `;` ` ` ` ` `// Function to return (x^y) % MOD` ` ` `// in O(log(y))` ` ` `static` `long` `power(` `long` `x,` ` ` `long` `y)` ` ` `{` ` ` `long` `res = ` `1` `;` ` ` `while` `(y > ` `0` `)` ` ` `{` ` ` `if` `((y & ` `1` `) != ` `0` `)` ` ` `res = (res * x) % MOD;` ` ` `x = (x * x) % MOD;` ` ` `y /= ` `2` `;` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` ` ` `// Function to return the count of distinct` ` ` `// graphs possible with n vertices` ` ` `static` `long` `countGraphs(` `int` `n)` ` ` `{` ` ` ` ` `// Maximum number of edges for a` ` ` `// graph with n vertices` ` ` `long` `x = n * (n - ` `1` `) / ` `2` `;` ` ` ` ` `// Function to calculate` ` ` `// (2^x) % mod` ` ` `return` `power(` `2` `, x);` ` ` `}` ` ` ` ` `// Driver code` ` ` `public` `static` `void` `main (String[] args)` ` ` `{` ` ` `int` `n = ` `5` `;` ` ` ` ` `System.out.println(countGraphs(n));` ` ` `}` `}` `// This code is contributed by AnkitRai01` |

## Python

`MOD ` `=` `int` `(` `1e9` `+` `7` `)` `# Function to return the count of distinct` `# graphs possible with n vertices` `def` `countGraphs(n):` ` ` `# Maximum number of edges for a` ` ` `# graph with n vertices` ` ` `x ` `=` `(n ` `*` `( n ` `-` `1` `)) ` `/` `/` `2` ` ` ` ` `# Return 2 ^ x` ` ` `return` `(` `pow` `(` `2` `, x, MOD))` `# Driver code` `n ` `=` `5` `print` `(countGraphs(n))` |

## C#

`// C# implementation of the approach` `using` `System;` `class` `GFG` `{` ` ` `static` `int` `MOD = (` `int` `)1e9 + 7;` ` ` ` ` `// Function to return (x^y) % MOD` ` ` `// in O(log(y))` ` ` `static` `long` `power(` `long` `x, ` `long` `y)` ` ` `{` ` ` `long` `res = 1;` ` ` `while` `(y > 0)` ` ` `{` ` ` `if` `((y & 1) != 0)` ` ` `res = (res * x) % MOD;` ` ` `x = (x * x) % MOD;` ` ` `y /= 2;` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` ` ` `// Function to return the count of distinct` ` ` `// graphs possible with n vertices` ` ` `static` `long` `countGraphs(` `int` `n)` ` ` `{` ` ` ` ` `// Maximum number of edges for a` ` ` `// graph with n vertices` ` ` `long` `x = n * (n - 1) / 2;` ` ` ` ` `// Function to calculate` ` ` `// (2^x) % mod` ` ` `return` `power(2, x);` ` ` `}` ` ` ` ` `// Driver code` ` ` `static` `public` `void` `Main ()` ` ` `{` ` ` `int` `n = 5;` ` ` ` ` `Console.Write(countGraphs(n));` ` ` `}` `}` `// This code is contributed by ajit.` |

## Javascript

`<script>` `// Javascript implementation of the approach` `const MOD = 1000000000 + 7;` `// Function to return (x^y) % MOD` `// in O(log(y))` `function` `power(x, y, MOD)` `{` ` ` `let res = 1;` ` ` `while` `(y > 0) {` ` ` `if` `(y & 1)` ` ` `res = (res * x) % MOD;` ` ` `x = (x * x) % MOD;` ` ` `y = parseInt(y / 2);` ` ` `}` ` ` `return` `res;` `}` `// Function to return the count of distinct` `// graphs possible with n vertices` `function` `countGraphs(n)` `{` ` ` `// Maximum number of edges for a` ` ` `// graph with n vertices` ` ` `let x = parseInt(n * (n - 1) / 2);` ` ` `// Function to calculate` ` ` `// (2^x) % mod` ` ` `return` `power(2, x, MOD);` `}` `// Driver code` ` ` `let n = 5;` ` ` `document.write(countGraphs(n));` `</script>` |

**Output:**

1024

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.