#1809. 火柴棒等式

火柴棒等式

题目描述

张琪曼:“你在做什么啊?”

李旭琳:“我在帮我的小侄子看作业呢,一会就好了。”

作业是:给你n\red{n}根火柴棍,你可以拼出多少个形如A+B=C\red{“A+B=C”}的等式?等式中的ABC\red{A、B、C}是用火柴棍拼出的整数(若该数非零,则最高位不能是0\red{0})。用火柴棍拼数字09\red{0\sim 9}的拼法如图所示。

img

(1)\red{(1)}加号与等号各自需要两根火柴棍

(2)\red{(2)} 如果AB\red{A≠B},则A+B=C\red{A+B=C}B+A=C\red{B+A=C}视为不同的等式ABC0\red{(A、B、C≥0)}

(3)\red{(3)}n\red{n}根火柴棍必须全部用上

输入格式

共一行,有一个整数nn24\red{n(n≤24)}

输出格式

共一行,表示能拼成的不同等式的数目。

样例

输入样例 1

14

输出样例 1

2

输入样例 2

18

输出样例 2

9

提示

样例 1\red{1} 解释:

2\red{2}个等式为0+1=1\red{0+1=1}1+0=1\red{1+0=1}

样例 2\red{2} 解释:

9\red{9}个等式为:

0+4=4\red{0+4=4}

0+11=11\red{0+11=11}

1+10=11\red{1+10=11}

2+2=4\red{2+2=4}

2+7=9\red{2+7=9}

4+0=4\red{4+0=4}

7+2=9\red{7+2=9}

10+1=11\red{10+1=11}

11+0=11\red{11+0=11}