104036 - 太阳能电池

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

Input

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

Output

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

Examples

Input

2

Output

3
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题