104036 - 太阳能电池

太空站需要将1×1和2×2两种规格的太阳能电池不重叠地铺满n×3的电池板上,求有多少种不同的铺设方案。

输入

一个整数n(0<n<110 000)。

输出

输出一个整数,即铺设方案数%12 345的值。

样例

输入

2

输出

3
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题