题目描述

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

输入格式

一行一个整数 $n$，$0 < n < 1,000$。

输出格式

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

样例

输入样例1

2

输出样例1

3

数据范围与提示