Minimum Coins and Ways

You are given an integer \(N\) (\(1 \le N \le 10^{18}\)). Imagine you have coins with denominations corresponding to powers of 2, that is, \(2^0, 2^1, 2^2, \ldots\). Each coin can be used at most once.

Your task is to determine:

• The minimum number of coins required to sum up exactly to \(N\).
• The number of different ways to choose such coins to achieve the sum \(N\).

Note: Due to the nature of coins being powers of 2, it turns out that the minimum number of coins is equal to the number of ones in the binary representation of \(N\) and there is exactly 1 way to form \(N\) using those coins.

For example, if \(N = 10\) (binary \(1010_2\)), the answer is (2, 1) because there are 2 ones in the binary representation and only one unique way to select these coins.

inputFormat

The input consists of a single integer \(N\) read from standard input.

outputFormat

Output two integers: the minimum number of coins and the number of ways to form \(N\) (which will always be 1), separated by a space, printed to standard output.

10

2 1