Counting Valid Piece Placements in Triangular Grids

A child is given a homework assignment to place chess pieces on several rows of boxes. For N rows, the first row has N boxes, the second row has N-1 boxes, and so on, until the N-th row has 1 box. In each row the pieces, if any, are placed in the leftmost boxes.

The rules for placement are as follows:

• The first row must have at least one piece (i.e. the number of pieces in row 1 is between 1 and N inclusive).
• For all subsequent rows (i > 1), if row i has c_i pieces, then it must satisfy \[ c_i \leq c_{i-1} \] and additionally you cannot place more pieces than there are boxes in that row (i.e. \(0 \le c_i \le N-i+1\)).

For example, when \(N=3\), the first row has 3 boxes, the second row has 2 boxes, and the third has 1 box. One possible sequence is \(c_1=3, c_2=2, c_3=1\). It turns out there are a total of \(13\) valid placements. Your task is to compute the total number of valid placements for a given N.

Note: The pieces in each row are always placed in the leftmost boxes.

inputFormat

The input consists of a single integer N (1 ≤ N ≤ 50), representing the number of rows (and the number of boxes in the first row).

outputFormat

Output a single integer, the number of valid ways to place the pieces subject to the given conditions.

sample

1

1