题目描述

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：\(F_0=0\),\(F_1=1\),\(F_n=F_{n-1}+F_{n-2},n>=2\)
任务：输入一个整数n(0<=n<=\(2^{60}\))，求出斐波那契数列的第n项mod 114514和前n项的和mod 114514。

输入数据

包含一个整数n(0<=n<=\(2^{60}\))，表示要求和的斐波那契数列长度。

输出数据

两个整数，分别为斐波那契数列的第n项mod 114514和前n项的和mod 114514的值。

输入

4

输出

3 7

样例解释：

1 1 2 3
\(F_4=3\)
\(\displaystyle\sum_{i=1}^4 F_i=7\)

说明/提示

数据规模与约定
对于30%的数据，n<=\(10^7\)
对于100%的数据，n<=\(2^{60}\)