题目描述

用红色的 11 和黑色的 22 两种规格的瓷砖不重叠地铺满 n*3 的路面，求出有多少种不同的铺设方案，结果模12345.

输入格式

仅仅包含一个整数 n。

输出格式

仅包含一个整数，表示铺设方案的数量。

2

3

提示

数据范围：0 < n < 1000 。