Problem Description

Given $n$ matchsticks, how many equations of the form $A+B=C$ can you form? The numbers $A$, $B$, and $C$ in the equation are integers formed using matchsticks (the highest digit cannot be zero unless the number is zero). The way to form the digits $0$ through $9$ with matchsticks is shown in the figure below:

Notes:

1. The plus sign and the equals sign each require two matchsticks.
2. If $A \neq B$, then $A+B=C$ and $B+A=C$ are considered different equations ($A, B, C \geq 0$).
3. All $n$ matchsticks must be used.

Input Format

A single integer $n$ ($1 \leq n \leq 24$).

Output Format

A single integer, the number of different equations that can be formed.

Sample Input and Output

Sample Input #1

14

Sample Output #1

2

Sample Input #2

18

Sample Output #2

9

Notes

Sample 1 Explanation:

The two equations are $0+1=1$ and $1+0=1$.

Sample 2 Explanation:

The nine equations are:

$0+4=4$, $0+11=11$, $1+10=11$, $2+2=4$, $2+7=9$, $4+0=4$, $7+2=9$, $10+1=11$, $11+0=11$.

This is the second question from the NOIP2008 Senior Group.

见题面 Input 部分

见题面 Output 部分