電電觀察兔子族群的個數，發現一開始有一對兔子，兩個單位時間後她們就可以繁殖出一對兔子；兔子永不死去。據此，我們可以歸納出兔子對數：\( F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-1} + F_{n-2} \) 你以為這題叫你算截至 \(n\) 單位時間前有幾對兔子ㄇ？？錯錯錯！！電電感興趣的是兔子所消耗之飼料的總和，其中每對兔子每單位時間須消耗一單位之飼料，所求即 \(\sum_{i=0}^{n-1}{F_i}\)。 兔子的個數由於很難算，因而被命名為「費事數列」，而這個數列之和自然就是「費事級數」惹。 因為答案顯然可能很大，所以請對 \(10^9+7\) 取模。

輸入格式

一非負整數 \(0 \leq n < 2^{31}\)。

輸出格式

請輸出 \(\displaystyle\sum_{i=0}^{n-1}{F_i}\)。

範例輸入 1

5

範例輸出 1

12

範例輸入 2

10

範例輸出 2

143

範例輸入 3

87

範例輸出 3

544858367

提示

子題說明

• 50% 測資 \(n < 40\)
• 30% 測資 \(n < 10^8\)
• 20% 測資無額外限制