Sum of Powers

Time limit2sMemory limit1024 MB

Summary

Find the n-th natural number k such that k divides 1 + 2^k + 3^k + 4^k + 5^k + 6^k, with n up to 65.

Level: Medium5 of 10
Topics: Number theory, Math, Brute force
Solved: No attempts yet

Problem

Seryozha loves studying numerical sequences. He has already studied every sequence that appears in books, so he asks all his acquaintances to invent one for him. His younger brother Romochka, who can only count to six, also asks for a sequence. After long explanations from Seryozha about what a sequence is, Romochka suggests that Seryozha study $1, 2, 3, 4, 5, 6$ . Seryozha has already studied that sequence many times, so he changed it slightly. Now he studies a sequence of natural numbers in which each term $k$ is a divisor of $1+2^k+3^k+4^k+5^k+6^k$ .

The first term of this sequence is $1$ , because $1+2+3+4+5+6 = 21$ and 21 is divisible by 1. The number 2 is not in this sequence, because $1+4+9+16+25+36=91$ is not divisible by 2. The number 3 is in this sequence, because $1+8+27+64+125+216=441$ and 441 is divisible by 3.

Seryozha computed a few terms of the sequence and then decided to write a program that computes the term with number $n$ . Write such a program.

Input

The input file contains a single integer $n$ ( $1 \le n \le 65$ ).

Output

Print the term of the sequence with number $n$ to the output file.

Examples2

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
2
```
Expected output
```
3
```