用两种规格的瓷砖不重叠地铺满一个 n \times 3 的矩形路面：

• 红色瓷砖：大小为 1 \times 1
• 黑色瓷砖：大小为 2 \times 2 （可旋转，但正方形旋转后不变）

两种瓷砖均可任意摆放，但必须完全覆盖路面，且不能重叠。求不同的铺设方案总数。由于答案可能非常大，请将结果对 ( 12345 ) 取模后输出。

输入只有一行，包含一个整数 n （ 0 < n < 10^{18} ）。

输出一个整数，表示方案数对 12345 取模后的结果。

样例说明

当 n=2 时，路面为 2 \times 3 。所有方案如下：

1. 全部使用 1 \times 1 瓷砖。
2. 在左侧两列放置一块 2 \times 2 黑色瓷砖，剩余位置用 1 \times 1 填充。
3. 在右侧两列放置一块 2 \times 2 黑色瓷砖，剩余位置用 1 \times 1 填充。

共 3 种方案，因此输出 3。

数据范围与约定

• 0 < n < 10^{18}

课课通