题目描述

给你n根火柴棍，你可以拼出多少个形如A+B=C的等式？

等式中的A、B、C是用火柴棍拼出的整数（若该数非0，最高位不能是0）。

用火柴棍拼数字0-9的拼法如下图所示：

注：

加号与等号各自需要两根火柴棍。

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

如果A≠B，则A+B=C与B+A=C视为不同的等式(A,B,C≥0)。

输入格式

一行一个整数n(1≤n≤24)。

输出格式

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

输入/输出样例

14

2

18

9

样例1解释

2个等式为0+1=1和1+0=1。

样例2解释

9个等式为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。

说明/提示

时间1000ms，内存256MiB