题目描述

一个由正整数组成的数列按照如下定义：

第一个数为 ： 最小的偶数

第二个数为 ： 最小的奇数

第三个数为 ： 最小的质数

之后的每个数均为 ：$a_{n} = 2 * a_{n − 1} - a_{n − 2}+ a_{n − 3} (n > 3)$。

编程求出该数列的第n（n<50）个数，数字可能比较大，数字需要对2147483647取模。

输入格式

输入一行一个整数 n

输出格式

输出一个整数为数列的第n个数

样例输入

3

样例输出

2