用两种规格的瓷砖不重叠地铺满一个 $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} $