提示: 欢迎访问OurACM平台。
Problem 1620 Revival's function

Accept: 27    Submit: 112
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Oaiei are learning math recently, he has found a very interesting question.

Given a number N, N can be divided into some integers which is some powers of 2.

We define f(N) is the number of methods which we can split N into some integers which is some powers of 2, and the appearances of each number is not exceed 2.

He would like to know the value of f (N) , and he asks you to calculate the exact value of f (N) / f (N-1).

If f (N) / f (N-1) is the repeating decimal, you should marked out the cycle section in brackets.

Input

There are multiple tests. For each test, there is an integer N(2<=N<=1000000).

Output

For each test, you should output two lines, the first line is the value of f (N) and the second line is the value of f (N) / f (N-1).

Sample Input

2 3 4 5

Sample Output

2 2 1 0.5 3 3 2 0.(6)

Source

Summer Training Qualification I

Submit  Back  Status  Discuss