582. How Many Orders Visit Everything

An undirected graph on n vertices is given. Count the sequences v1, v2, ..., vn that use every vertex exactly once and in which each consecutive pair is joined by an edge.

Two sequences that are reverses of each other count separately. Print the count modulo 1000000007.

4 vertices in a cycle 1-2-3-4-1 -> 8 4 vertices in a star -> 0 the centre would have to be used twice

## The same table as 581

This is problem 581 with min replaced by +, and the starting cost replaced by a starting count of 1.

dp[mask][u] = the number of orders that use exactly the vertices in mask and end at u dp[1<<i][i] = 1 for every i dp[mask | 1<<v][v] += dp[mask][u] when u is in mask and u-v is an edge answer = sum over u of dp[full][u]

Every vertex is a possible start, so there are n base cases here rather than the single one in 581.

## Why the answer counts both directions

A path and its reverse are different SEQUENCES, and the table counts sequences. Reporting undirected paths would need a division by 2, which is wrong when n = 1: there is one sequence and it is its own reverse.

The statement therefore asks for sequences, which needs no division and no special case. When a counting problem seems to want a division, check the fixed points first.

## Where the modulus goes

Reduce after every addition. The count can reach n!, which passes 10^9 at n = 13, so an unreduced accumulator overflows well inside the constraints.

## Reading the answer

The star answers 0. Its centre lies on every edge, so any order using all four vertices would have to pass through the centre twice, and a sequence uses each vertex once.

The complete graph on 4 answers 24, which is 4!: every order works. Those two are the extremes and are worth checking first in any implementation.

## Cost

Time O(2^n * n^2). Space O(2^n * n).

At n = 16 that is about 17 million steps.

Constraints - `1 ≤ n ≤ 16` - `0 ≤ m ≤ n(n-1)/2` - no self loops and no repeated edge