Find the number of degree n irreducible polynomials over GF(2). For example: for n=1 there are two such polynomials: x and x+1. For n=2 there is only one: x²+x+1. Note that in R[x] the polynomials x²+1 is irreducible, but not over GF(2), because x²+1 = (x+1)*(x+1)

Input

A single positive integer n, where n < 500000.

Output

Output the answer for n.

Example

Input:
201

Output:
15989433276208858463104100421305100522608250813995004946218

Input:
1

Output:
2

Input:
2

Output:
1

Input:
3

Output:
2