Сумма степеней

시간 제한2초메모리 제한1024 MB

요약

1+2^k+3^k+4^k+5^k+6^k이 k로 나누어떨어지는 양의 정수 k 가운데 n번째 값을 구합니다. n은 65 이하입니다.

난이도: 어려움10점 중 8점
유형: 정수론, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

Мальчик Сережа очень любит изучать числовые последовательности. Он уже изучил все числовые последовательности, встречающиеся в книгах, и теперь просит всех своих знакомых придумать ему последовательность. Также он попросил придумать числовую последовательность и своего младшего брата Ромочку, который умеет считать только до шести. Разумеется, Ромочка (после долгих рассказов Сережи о том, что такое последовательность) предложил Сереже изучить последовательность $1, 2, 3, 4, 5, 6$ . Но Сережа уже неоднократно изучал эту последовательность, и немного изменил ее. Теперь он изучает последовательность натуральных чисел, такую, что каждый ее член $k$ является делителем числа $1+2^k+3^k+4^k+5^k+6^k$ .

Например, первым числом в этой последовательности является $1$ , так как $1+2+3+4+5+6 = 21$ и это число делится на единицу. Двойка в эту последовательность не входит, так как $1+4+9+16+25+36=91$ не делится на $2$ . Число $3$ в эту последовательность также входит, так как $1+8+27+64+125+216=441$ и делится на $3$ .

Сережа вычислил несколько первых членов последовательности, после чего решил, что лучше напишет программу, которая за него посчитает член последовательности с номером $n$ . Напишите и Вы такую программу.

입력

Входной файл содержит единственное число $n$ ( $1 \le n \le 65$ ).

출력

В выходной файл выведите искомый член последовательности.

예제2

예제 1
입력
```
1
```
예상 출력
```
1
```
예제 2
입력
```
2
```
예상 출력
```
3
```