GF2 - Irreducible polynomials over GF2

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: x2+x+1. Note that in R[x] the polynomials x2+1 is irreducible, but not over GF(2), because x2+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

Added by:Robert Gerbicz
Date:2009-05-25
Time limit:0.100s-1s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:classic problem, own input

hide comments
2009-05-26 08:31:50 [Trichromatic] XilinX
I've solved this problem in MIPT Online Judge by Ruby, but it seems that Ruby works pretty slow in SPOJ.

Last edit: 2009-05-26 02:21:16
2009-05-26 08:31:50 Robert Gerbicz
Java and Python are too slow on this problem. You can try c/c++ or haskell.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.