岳的背叛

• 时间限制：5 秒
• 内存限制：512 MB
• 输入：标准输入
• 输出：标准输出

弗拉基米尔·哈克南男爵绑架了威灵顿·岳（莱托·阿特雷德斯公爵的私人医生）的妻子。为了救回妻子，岳必须背叛公爵并解除城市防御。要解除覆盖城市的力场护盾，需要输入一段特殊代码。

岳知道代码满足：
- 由数字 $1$ 到 $9$ 组成；
- 长度恰好为 $2n$；
- 前 $n$ 位数字之和与后 $n$ 位数字之差不大于 $1$；
- 前 $n$ 位数字之积等于后 $n$ 位数字之积。

帮助岳求出有多少个长度为 $2n$ 的代码，以便他能救回妻子。

输入数据

给出一个整数 $n$，其中 $2n$ 是解除护盾的代码长度（$1 \le n \le 42$）。

输出数据

输出长度为 $2n$ 的代码数量。

评分系统

本题共有 42 个测试点，所有测试点独立计分。

样例

样例输入 1

1

样例输出 1

9

样例输入 2

2

样例输出 2

177

注释

第二个样例中，符合条件的代码有：
- $9$ 个由四个相同数字组成的代码；
- $9 \times 8 \times 2 = 144$ 个代码，其中前两位数字不同，且与后两位数字以某种顺序相同；
- $4$ 个代码，由一半的数字 $1$ 和 $4$、另一半的两个数字 $2$ 组成；
- $8$ 个代码，由一半的数字 $2$ 和 $6$、另一半的数字 $3$ 和 $4$ 组成；
- $8$ 个代码，由一半的数字 $3$ 和 $8$、另一半的数字 $4$ 和 $6$ 组成；
- $4$ 个代码，由一半的数字 $4$ 和 $9$、另一半的两个数字 $6$ 组成。