测试数据来自 wjszez/1666

【问题描述】
用1*1和2*2两种规格的磁砖不重叠地铺满n*3的地板，求出有多少种不同的
铺设方案。
【输入格式】
一行一个整数n。

【输出格式】
一行一个整数，为结果模12345的值。
【输入样例】
2
【输出样例】
3
【数据规模】
对 100%的数据满足：0<n<1000。