#6264. friend-斐波那契
题目描述
求 ， 其中 代表斐波那契数列的第 项。
当然结果会很大，请将它对 取模。
输入格式
一行一个数 .
输出格式
一行一个数，代表答案。
样例
样例输入
6样例输出
104数据范围与提示
对于30%的数据：。
对于另外20%的数据: （即n是1000000的倍数），且。
对于100%的数据：。
题目来源：fps-loj-small-pics.zip；FPS 共享题包，题包内第 214 题。保留原作者与原赛事署名。
图灵 OJTURING / ONLINE JUDGE