1430 - 铺瓷砖

通过次数

23

提交次数

48

时间限制 : 1 秒
内存限制 : 64 MB

用红色的1*1和黑色的2*2两种规格的瓷砖不重叠地铺满n*3的路面,求出有多少种不同的铺设方案。

输入

一行一个整数n,0<n<10^18。

输出

一行一个整数,为铺设方案的数量模12345的结果。

样例

输入

2

输出

3

来源

课课通