H-数列求和_2022河南萌新联赛第（六）场：郑州大学

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小林最近在学习斐波那契数列，他发现斐波那契有着很神奇的性质，这些性质也同样体现在斐波那契的衍生数列上。众所周知，原始的斐波那契是 $F_1=1$ ， $F_2=1$ ，当 $i$ 大于 $3$ 时有 $F_i=F_{i-1}+F_{i-2}$ 。小林现在想知道，他假如 $F_1$ 不变仍然为 $1$ ， $F_2$ 变为 $3$ ， $i$ 大于等于 $3$ 时的规则不变，再按照斐波那契数列的方式重新生成一个序列，那么新的数列的前 $n$ 项和是多少呢？

最终结果可能会比较大，最后算出的答案对 $1e11+3$ 取模即可。

输入描述:

一行一个正整数。

输出描述:

输出一行一个整数为你的答案。

示例1

输入

复制

输出

复制