题目描述

小明根据斐波那契数列构造出了另一种数列，“奇偶斐波那契数列”，它的定义如下：

对于奇偶斐波那契数列的第$i(i>2)$项$f(i)$，有

$$f(i)= \begin{cases} 0, & i = 1 \\ 1, & i = 2\\f(i-1)+f(i-2), & \text{if $i$ is odd}\\ f(i-1)-f(i-2), & \text{if $i$ is even} \end{cases}$$

现在小明想知道这个数列的第 $n$ 项对 $114514$ 取模的结果是多少，请你帮他解决这个问题。

输入格式

一行，一个正整数 $n$。

输出格式

输出答案对 $114514$ 取模的结果。

输入输出样例

5

1

7

2

样例解释

该数列为$0,1,1,0,1,1,2\cdots$。第5项是1，第7项是2。

数据范围

对于$30\%$的数据，有$1 \le n \le 50$。

对于$70\%$的数据，有$1\le n\le10^5$。

对于$100\%$的数据，有$1\le n\le10^7$。

提示

odd 译为奇数, even 译为偶数。

由于数列后期增长速度飞快，为了防止数据过大，需要对答案进行取模操作。例：114518对114514取模为$114518 \% 114514 = 4$。