问题描述

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

输入数据

从problem2.in中读入一个数N。1<=N<=1000。

输出数据

将答案输出到problem2.out中。由于结果可能很大，你只需要输出这个答案% 12345的值

样例输入：

2

样例输出：

3