Description

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

Input Format

仅仅包含一个整数 n。

Output Format

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

2

3

Hint

数据范围：0 < n < 1000 。