A word of length *n* is "rich" if it contains, as subwords, exactly *n* distinct palindromes. You shoud find the number of binary rich words of length *i* for all *i* from 1 to *n*.

### Input

The input contains an integer *n* (1 ≤ *n* ≤ 61).

### Output

### Sample

**Problem Author: **Mikhail Rubinchik

**Problem Source: **Palindromic Contest, July 11, 2015