Problem Statement

In the Kingdom of Numis, a grand treasury of N ancient coins has been discovered, each bearing a unique inscription on both its front and back. The inscriptions are not random; they are two different sequences—one for the front (P sequence) and one for the back (Q sequence). Each sequence contains all numbers from 1 to N in some shuffled order, making each coin uniquely numbered. The kingdom's scholars believe that a powerful ritual of prosperity can be performed if they can select a subset of these coins in such a way that every number from 1 to N is represented at least once—either in the front or the back of the chosen coins. However, choosing the right subset is a challenge, and they must determine in how many different ways they can accomplish this task. As the kingdom's chief mathematician, the responsibility falls upon you to calculate the number of valid ways to select the subset of coins that ensures complete coverage of all numbers. The fate of Numis's prosperity rests in you