Lotus Planting Challenge

John is helping Bessie complete her lotus planting task in a special field. The field has n cells in which a lotus must be planted. Among these cells, m cells have platinum-rich soil, in which a lotus cannot be planted directly. In order to plant a lotus in a platinum cell, John must first mine the platinum (which costs 1 stamina) and then plant the lotus (which also costs 1 stamina). For cells with normal soil, a lotus can be planted directly at a cost of 1 stamina.

Thus, for a normal cell the cost is 1, and for a platinum cell the cost is 2. Since every platinum cell must be mined before planting, the minimum total stamina consumption required to complete the task is

[ S = (n - m) + 2m = n + m. ]

If John has only P stamina available, then the task can be completed only if P \geq S. Otherwise, output -1.

In this problem, we also wish to count the number of different action sequences that complete the task using exactly S stamina. Note that the actions for the normal cells consist of a single planting operation (cost 1) and each platinum cell requires a pair of operations: first mining (cost 1) then planting (cost 1). All cells are considered distinct, and the order in which John performs the operations matters, with the only restriction that for every platinum cell, the mining must occur before its planting.

Let W_S be the number of valid sequences that complete the task using exactly S stamina. It can be shown that

[ W_S = \frac{(n+m)!}{2^m}, ]

since there are a total of n-m+2m = n+m operations and for each platinum cell the two operations must appear in order (giving a division by 2 for each platinum cell).

Furthermore, since mining platinum is beneficial, let G be the maximum number of platinum cells mined when completing the task using exactly S stamina, and let W_G be the number of sequences achieving that maximum. Notice that in order to successfully plant a lotus in a platinum cell, the platinum must be mined; thus if m > 0 then we always mine all m platinum cells so that G = m and W_G = W_S. If there are no platinum cells (i.e. m = 0), then the task does not involve any platinum mining, and in that case output -1 for the second line.

In summary, you are given three integers: n, m and P. Compute:

• If P < n + m, output just -1.
• Otherwise, output on the first line two space‐separated integers: S = n + m and W_S = (n+m)! / 2^m.
• On the second line, if m > 0 output two space‐separated integers: G = m and W_G = W_S; if m = 0, output just -1.

Note: It is guaranteed that all intermediate results fit in a 64-bit signed integer.

inputFormat

The input consists of a single line containing three space‐separated integers n, m and P, where:

• n (1 ≤ n ≤ 20) is the total number of lotus cells to be planted,
• m (0 ≤ m ≤ n) is the number of cells with platinum-rich soil (which require mining before planting),
• P (1 ≤ P ≤ 10⁹) is the amount of stamina John has initially.

outputFormat

If P < S (i.e. P < n + m) then output a single line containing -1 (without quotes). Otherwise, output two lines:

• The first line contains two space‐separated integers: S and W_S.
• The second line: if any platinum cell exists (m > 0), output two space‐separated integers G and W_G; otherwise (if m = 0) output -1.

sample

3 1 4

4 12
1 12