Submission #2094683

---

Source Code Expand

using System;
using System.Linq;
using System.Collections.Generic;
class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int mod = 1000000007;
        long[] fibonacci = new long[1000010];
        fibonacci[0] = n;
        fibonacci[1] = 0;
        for (int i = 2; i < fibonacci.Length; i++) fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % mod;

        long res = 0;
        long ress = 0;
        
        for (int i = 0; i < n; i++)
        {
            //-1-n-m-m-m... 全てのn-m分岐点において可能性あり
            res = (res + fibonacci[i]) % mod;

            //n-1-...-1-m-1-... 現在まで続いている可能性のある分岐点の数
            ress = (ress + (i + 1) * fibonacci[i]) % mod;
        }
        //2,3,...,nが入るので
        res = (res * (n - 1)) % mod;
        Console.WriteLine((res + ress ) % mod);
    }
}

Submission Info

Judge Result