In a previous Concurso Anual de Programación "Donald Knuth", Rem faced a peculiar problem: counting the number of different ways to travel across a hive-shaped grid.

The grid is formed by columns of hexagonal cells:

• The first column has exactly 1 cell.
• The second column has 2 cells.
• The third column has 3 cells.
• $$$\dots$$$
• The $$$(n+1)$$$-th column has $$$n+1$$$ cells.
• After that, each subsequent column has one fewer cell than the previous, until the final $$$(2n+1)$$$-th column which has exactly 1 cell.

Thus, the grid consists of $$$2n+1$$$ columns of hexagonal cells, forming the shape of a "diamond hive." The entry cell is the single hexagon in the first column, and the storage cell is the single hexagon in the last column.

Below is an example of the grid with size $$$n=3$$$ with the valid set of movements for a single cell:

Rem solved the original challenge: finding how many paths exist from the entry to the storage without visiting the same hexagonal cell twice.

Later, he wondered: "If someone naïvely tried to simulate every single path with a brute-force depth-first search, how many total steps would such an algorithm actually take?"

In this brute-force simulation, for each valid path, a DFS would traverse the entire path from beginning to end. Therefore, the total cost of this approach equals the sum of the lengths of all distinct paths, where the length of a path is the number of hexagonal cells it visits.

Your task is to compute the sum of the lengths of all distinct paths.