You are given an integer n representing the total number of playing cards.

A house of cards is constructed according to the following rules:

• It is composed of $1$ or more rows.

• Each row consists of some positive number of triangles. A single triangle is formed by leaning $2$ cards against each other.

• In a row containing $k$ triangles, exactly $1$ horizontal card is placed between every $2$ adjacent triangles, resulting in $k - 1$ horizontal cards. Consequently, a row with $k$ triangles uses a total of $3k - 1$ cards.

• Every row above the bottom row must have strictly fewer triangles than the row directly below it.

• The structure must use all n cards.

Return the total number of distinct valid houses of cards that can be built using exactly n cards.

Constraints:

• $1 \leq$ n $\leq 500$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.