104036 - 太阳能电池

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

输入

一个整数n（0＜n＜110 000）。

输出

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

样例

输入

2

输出

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