← 返回比赛

已结束黑龙江工程学院第十一届程序设计竞赛

← 上一题下一题 →

A4827 | $最熟悉的陌生人$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

在炉石传说的酒馆里，鲍勃正在研究一种强大的召唤法术——斐波那契召唤术。他发现，每当他召唤第 $n$ 个随从时，消耗的法力值遵循某种神秘的规律： 召唤第 $1$ 个随从需要 $1$ 点法力值。 召唤第 $2$ 个随从需要 $1$ 点法力值。 从第 $3$ 个开始，每个随从的召唤消耗等于前两个随从消耗之和。 然而，由于法力水晶的限制，卡德加只能计算召唤第 $n$ 个随从时消耗的法力值对 $1,000,000,007$ 取模后的结果（防止法力溢出爆炸💥）。 给定一个整数 $n$ ，求斐波那契召唤术在第 n 次召唤时消耗的法力值，即求斐波那契数列第 $n$ 项 $mod 1,000,000,007$。

输入格式

一个整数 $n$。 数据范围：$（1≤n≤2^{63}）$

输出格式

一个整数，表示 $f(n)$ $mod$ $1,000,000,007$。

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

C++ 编辑器

输入

输出