题目描述

训练营要布置一条彩灯长廊。老师把彩灯分成一段一段来设计，每一段都有若干种接法。

第 1 段彩灯有 1 种接法，第 2 段彩灯有 3 种接法。

从第 3 段开始，老师规定：第 i 段彩灯的接法数，等于前一段接法数加上前两段接法数。

请问第 n 段彩灯有多少种接法？

由于答案可能很大，请输出答案对 1000000007 取模后的结果。

输入格式

输入一个整数 n。

输出一行，一个整数，表示第 n 段彩灯接法数对 1000000007 取模后的结果。

前 5 段的接法数依次为 1, 3, 4, 7, 11。