Enumeration of Tournaments

Suppose that $n$ players participate in a single-elimination tournament. The tournament goes round by round. Let $k$ be the number of remaining players at the beginning of a round. The players then form $\lfloor \frac{k}{2} \rfloor$ random pairs, and every possible partition into pairs is equally likely. In each pair, the two players play one game, the one with the higher rating wins, and the loser leaves the tournament. The remaining $\lfloor \frac{k + 1}{2} \rfloor$ players advance to the next round.

Each participant has a unique rating, and the result of each game is fully determined by the ratings: the player with the higher rating always wins. The only thing that affects the schedule of the tournament is the random pairing made in each round. Count the number of different tournaments that could occur. Two tournaments are different if some game between two participants occurs in one of them but not in the other.

The answer can be large, so output it modulo $2^{64}$.

The input contains one integer $n$, the initial number of players ($1 \le n \le 10^{18}$).

Output the number of different tournaments modulo $2^{64}$.