题目描述

用 1x1 和 2x2 两种尺寸的瓷砖不重叠地铺满 Nx3 大小的地板，共有多少种方案？

输入格式

一个整数 N。

输出格式

由于结果可能很大，你只需要输出这个答案 mod 12345 的值。

样例

2

3

数据范围

$1≤N≤1000$

来源

信友队