Partition of a number#2338

Partition of a number

1 second
64 megabytes
Medium

Let us define the number as follows: n! = 1 \cdot 2 \cdot \ldots \cdot n if n > 0, and n! = 1 if n = 0. Let C(n, k) = \frac{n!}{k!(n - k)!} if 0 \leq k \leq n, and C(n, k) = 0 if k > n.

This number equals the number of combinations of elements taken at a time. In mathematics, such numbers are called binomial coefficients.

You are to represent the given number as the sum of three binomial coefficients:

P = C(a, 0) + C(b, 1) + C(c, 2),

where 0 \leq a < b < c.

Input

The input file contains a single number (1 \leq P \leq 10^{18}).

Output

In the output file, print the required numbers , , (0 \leq a < b < c). Print three zeros if there is no solution.

Examples

Example 1

Loading
Loading