은빛 별, 홀로 서다

태양계 거리를 잴 때 쓰는 표준 길이 단위 가운데 하나는 천문단위이며, AU로 줄여 쓴다. 이 문제에서도 AU를 쓴다.

탐사선이 화성에서 조립되고 있으며 곧 발사된다. 탐사선의 목적지는 예상 밖으로 밝은 자외선 반사율 덕분에 은빛 별이라는 이름이 붙은 소행성이다. 탐사선의 여정은 길고, 도중에 다른 소행성 몇 개를 들를 수도 있다. 은빛 별을 포함해 들를 후보 소행성들은 화성에서 은빛 별로 가는 경로 위에 있도록, 그리고 화성에서의 거리를 AU로 나타내어 오름차순으로 나열하면 처음 몇 개의 소수 2, 3, 5, 7, 11, ... 의 수열이 되도록 신중하게 골랐다. 여정에서 발사 지점과 은빛 별 사이의 모든 소행성을 반드시 들을 필요는 없다. 반면에 연속해서 들르는 두 소행성 사이의 거리는 많아야 14 AU이다. 그렇지 않으면 탐사선이 충분한 과학 데이터를 모으지 못한다. 어느 쪽도 어길 수 없는 두 가지 규칙이 있다. 첫째, 가장 가까운 소행성, 즉 거리 2 AU에 있는 소행성을 들른다. 둘째, 은빛 별을 들른다.

어떤 소행성을 들르는지에 따라 탐사선의 가능한 궤적이 여러 가지 있다. 두 궤적에서 들르는 소행성의 수열이 적어도 하나의 소행성에서 다르면 두 궤적은 서로 다른 것으로 본다. 그렇지 않으면 같은 것으로 본다. 각 궤적에는 발사 지점 소행성과 은빛 별이 들어 있다. 탐사선은 은빛 별을 향해 꾸준히 나아가며 결코 되돌아가지 않는다. 탐사선 항법 팀은 가장 유망한 궤적들을 평가해야 한다. 이를 위해 먼저 서로 다른 모든 탐사선 궤적의 수를 계산하려 한다.

입력은 한 줄로 이루어지며, 화성에서 은빛 별까지의 거리를 AU로 나타낸 정수 P (2 ≤ P ≤ 211) 하나가 주어진다. P는 소수이다.

서로 다른 탐사선 궤적의 수를 출력한다.