题目描述

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

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

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

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

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

输入格式

输入一个正整数$n$

输出格式

输出斐波那契数列的前$n$项和，并对$100007$取余

样例数据

10

143

数据范围

$1\leq n \leq 10^6$