题目描述

すぬけ君拥有无限多的正方形瓷砖和正三角形瓷砖。这些瓷砖的边长均为 $1$。请问，使用这些瓷砖，有多少种方法可以拼出一个边长为 $d$ 的正十二边形？请将答案对 $998244353$ 取模后输出。

更为严格地说：

• 使用瓷砖的数量没有限制。
• 任何两块使用的瓷砖都不能重叠。
• 所有使用的瓷砖所覆盖的区域的并集，必须是一个没有空洞的正十二边形。
• 对于两种拼法，如果通过旋转和平移（不允许镜像）可以使一种拼法中的每一块瓷砖与另一种拼法中的同类型瓷砖完全重合，则认为这两种拼法是相同的。

输入格式

输入从标准输入读取，格式如下：

$d$

输出格式

请输出答案。

样例 1

输入

1

输出

1

说明/提示

限制条件

• $1 \leq d \leq 10^6$
• 输入中的所有数值均为整数。

样例解释 1

唯一的拼法如下图所示。

由 ChatGPT 4.1 翻译