토너먼트 경우의 수 세기

$n$명의 선수가 단판 토너먼트에 참가한다. 토너먼트는 라운드 단위로 진행된다. 라운드 시작 시점에 남은 선수 수를 $k$라고 하자. 선수들은 무작위로 $\lfloor \frac{k}{2} \rfloor$개의 쌍을 이룬다. 가능한 쌍 배정은 모두 같은 확률로 선택된다. 각 쌍에서 두 선수가 한 경기를 치르고, 한 명이 이긴다. 진 선수는 토너먼트에서 탈락한다. 남은 $\lfloor \frac{k + 1}{2} \rfloor$명이 다음 라운드에 진출한다.

각 선수의 레이팅은 서로 다르며, 경기 결과는 레이팅으로 완전히 정해진다. 레이팅이 높은 선수가 항상 이긴다. 따라서 토너먼트 진행에 영향을 주는 것은 라운드마다 이루어지는 무작위 쌍 배정뿐이다. 일어날 수 있는 서로 다른 토너먼트의 수를 구하라. 두 토너먼트 중 한쪽에만 나타나는 경기(두 선수 사이의 대결)가 있으면 두 토너먼트는 서로 다르다.

답이 클 수 있으므로 $2^{64}$로 나눈 나머지를 구하라.

정수 $n$ 하나가 주어진다. $n$은 처음 참가하는 선수 수이다 ($1 \le n \le 10^{18}$).

가능한 서로 다른 토너먼트의 수를 $2^{64}$로 나눈 나머지를 출력한다.