TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5029
  • Problem
  • P5029斐波那契数列
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s 512m
    Description

    定义一个数列:

    \(f(0)=a,f(1)=b, f(n)=f(n-1)+f(n-2)\)

    其中 \(a,b\) 均为正整数,\(n\geq2\)

    问有多少种 \((a,b)\) ,使得 \(k\) 出现在这个数列里,且不是前两项。

    由于答案可能很大,你只需要输出答案模 $10^9+7$ 的结果即可。

    Input Format

    一行一个整数 \(k\)

    Output Format

    一行一个整数,表示答案模 $10^9+7$ 的结果

    Sample Input 1

    19260817

    Sample Output 1

    34166325

    Sample Input 2

    1000000000

    Sample Output 2

    773877569

    Hint

    $1\leq k\leq10^9$


    Source  洛谷3986