Dnipro Conquers Space

Everyone knows that Dnipropetrovsk is the space capital of Ukraine. The Southern Machine-Building Plant produces launch vehicles, engines, and other space exploration devices that are recognized worldwide. For instance, the American Antares launch vehicle was recently launched using engines made at the Yuzhnoye Design Bureau. Dnipropetrovsk's contributions to space exploration continue to grow.

A critical task for spacecraft is maintaining communication with Earth. To model this process, a permutation of natural numbers from $1$ to $n$ is sent to a computer. However, errors can occur during data transmission, so instead of a specific number $a$, the numbers a-1, $a$, or a+1 might be received. Our goal is to reconstruct the original permutation from the received data. Unfortunately, it's not always possible to do this uniquely. Your challenge, as a participant in the traditional All-Ukrainian competition "Peaceful Space," is to determine how many different permutations could have resulted from the received data set.