题目描述

用红色的 $1\times1$ 瓷砖和黑色的 $2\times2$ 瓷砖，不重叠、不留空隙地铺满 $n\times3$ 的矩形。求不同铺法的数量，对 $12345$ 取模。

输入格式

一行一个整数 $n$。

输出格式

输出方案数模 $12345$ 的结果。

样例

2

3

数据范围

$1\le n<1000$。