Problem B. Mirror for numbers

Author:Anton Karabanov   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  


A backwater city of N is populated by natural numbers. Today they have a holiday, so the amusement park has a new attraction — the numeric mirror. It works like this: number is translated into binary numeral system, its digits are mirrored in reverse order (if the binary representation was tailed by one or more zeroes, they are discarded). The resulting binary string is translated back to a natural number. For example, if the number 26 will come to the mirror, its binary representation 2610 = 110102 will be reversed to 10112 (resulting leading zero is discarded) and everybody will see number 11 in the mirror.

Every number with binary representation of exactly d digits has come to the mirror one by one. Determine how many of them have seen their image in the mirror to be ...

  1. less than the original number;
  2. equal to the original number;
  3. greater than the original number.

Input format

Input contains a natural number d.

Output format

Output three integers, one per line — answer to the problem.


1 ≤ d ≤ 50

Notes on the sample

In the sample d = 4. Mirror was approached by all numbers with the binary length of 4 digits, i.e. numbers from 8 to 15.

Number 8 is mirrored as 1, 9 as 9, 10 as 5, 11 as 13, 12 as 3, 13 as 11, 14 as 7 and 15 as 15.

In total, five numbers are mirrored as lesser than originals (8, 10, 12, 13 and 14), two do not change (9 and 15), one is mirrored as greater than original (11).

Sample tests

No. Standard input Standard output

0.087s 0.017s 15