题目描述

已知斐波那契数列是一个特殊的数列，性质如下：

第一项： $f(1) = 1$

第二项： $f(2) = 1$

第$n$项： $f(n) = f(n-1) + f(n-2),\ \ \ (3 \leq n)$

请你求出斐波那契数列前$n$项的和，这个值可能会很大，需要模 $5382500$

输入格式

输入一个整数$n$

输出格式

输出斐波那契数列前$n$的和

样例数据

10

143

提示

这是一道模板题，做之前你需要掌握矩阵快速幂的相关知识

$1\leq n \leq 10^{15}$

对于$40\%$的数据：$n \leq 10^6$

对于$100\%$的数据：$n \leq 10^{15}$