65087 - [NOIP2008 提高组] 火柴棒等式 matches

通过次数

0

提交次数

0

时间限制 : 1 秒
内存限制 : 128 MB

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

注意:

  1. 加号与等号各自需要两根火柴棍;

  2. 如果 A\neq B,则 A+B=CB+A=C 视为不同的等式(A,B,C\geq0);

  3. n 根火柴棍必须全部用上。

输入

一个整数 n(1 \leq n\leq 24)

输出

一个整数,能拼成的不同等式的数目。

样例

输入

14

输出

2

输入

18

输出

9

提示

【输入输出样例 1 解释】

2 个等式为 0+1=11+0=1

【输入输出样例 2 解释】

9 个等式为

0+4=40+11=111+10=112+2=42+7=94+0=47+2=910+1=1111+0=11