Count Staircase Constructions

You are given n bricks. Your task is to determine the number of different ways to construct a staircase by arranging all n bricks such that each step has strictly more bricks than the previous one. In other words, you need to count the number of partitions of n into at least two distinct positive integers.

The problem can be mathematically formulated as follows: find the number of solutions for

\( n = a_1 + a_2 + \cdots + a_k \) where \( a_1 < a_2 < \cdots < a_k \) and \( k \ge 2 \).

Note: The solution should be computed using the idea of dynamic programming, where a 2D array is maintained to count the number of ways to partition the number using distinct summands. The final answer is adjusted by subtracting the trivial partition which consists of a single step.

inputFormat

The input consists of a single integer n (\(1 \le n \le 100\)) representing the total number of bricks.

Input is provided via stdin.

outputFormat

Output a single integer representing the number of ways to build a staircase as described above. The output should be printed to stdout.

1

0