Problem Statement

Deep in the archives of the Kingdom of Numis, historians unearthed a hoard of N ancient coins, each engraved with a unique inscription on its front and back. These inscriptions form two separate sequences — one running across the fronts (call it sequence P) and one across the backs (sequence Q). Both sequences are permutations of the numbers 1 through N, so every coin ends up carrying a unique pairing. According to legend, a ceremony of prosperity can only be performed if the historians pick out a subset of coins such that every number from 1 to N shows up somewhere among the fronts or backs of the chosen coins. Figuring out which subsets qualify isn't obvious, and they need to know exactly how many such subsets exist. As the resident mathematician of Numis, it falls to you to count the number of subsets of coins that leave no number from 1 to N uncovered. The kingdom's fortunes hinge on getting this count right — can you work it out? Input Format The first line contains an integer, N