Hi. I have encountered this problem recently and didn't know how to approach it.

We want to construct compounds with these properties:

• C has 4 links and can bond with either C, H or I
• H can bond with C only through 1 link
• I can bond with C only through 2 links
• there is no atom with one or more free links

For example, H-C=C is not a compound because the middle C needs another link and the right one 2 more.

Two compounds are different if the numbers of C, H or I differ.

Now we define the mass of a compound as 4 * no. of C + 2 * no. of I + no. of H.

Task

Given 30 <= N <= 100000, find how many compounds with mass N there are with at least one C, I and H.

Example:

Input: N = 40

Output: 3

Explanation

These are the only possible compounds with mass 40: