题目描述

用$1 × 1$和$2 × 2$的地砖不重叠地铺满$N × 3$的地板，共有多少种方案？

输入格式

一个数字$N<=1000$

输出格式

所求的答案$mod 12345$

样例 #1

样例输入 #1

2

样例输出 #1

3