Minimum Coin Set for Complete Value Coverage

In celebration of Wildcat's Birthday, a group of OIers decided to buy a birthday cake without the hassle of making change, regardless of the cake's final price. They only know an estimated upper bound n for the cake price, and they want to pay exactly without needing change.

This leads to the following problem: Given a positive integer n, is it possible to choose a set of k distinct positive integers (coins) such that every integer in the range [1, n] can be represented as the sum of some subset of these coins? If possible, determine the minimum number k required and the number of different ways to choose such a coin set.

The coin set {a₁, a₂, ..., a_k} must satisfy the following conditions (with coins in increasing order):

[ \begin{cases} a_1 = 1,\[6pt] a_i \le \left(\sum_{j=1}^{i-1} a_j\right) + 1 \quad \text{for } i \ge 2. \end{cases} ]

Note that the total sum \(S = \sum_{i=1}^{k}a_i\) may be larger than n, but it must be at least n so that every value from 1 to n is representable.

Input Format: A single positive integer n.

Output Format: Two integers separated by a space: the minimum number of coins k and the number of different ways to choose such a set.

Example:

• For n = 4, the minimum number is 3 and there are 2 ways: {1, 2, 3} and {1, 2, 4}.

inputFormat

The input is a single positive integer n representing the maximum value that needs to be covered.

outputFormat

Output two integers separated by a space: the minimum number of coins k and the number of different ways to select a coin set that is capable of representing every integer from 1 to n as the sum of some subset of its coins.

sample

1

1 1