Areesha likes to play interesting games with her friend Adam. The game they played last evening is about building a number with n digits.

They start with a number without any digits. There will be n moves. In each move players append one digit to a number — so a new digit will be the last digit after the move. The only rule is: after every appended digit, the number has to be divisible by this digit. It implies that they can never add a digit 0.

Adam thinks the game is easy, because there are many numbers they can get at the end. But how many are there? Count numbers they can get, modulo $2^{32}$.

Input format

The only line of the input contains one integer n — the number of times players will append a digit.

Output format

Print the number of numbers Adam and Areesha can get, modulo $2^{32}$.

Constraints

• $1 \le n \le 10^{18}$