该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个整数 n，请问满足以下条件的独立集有几个？

其一，集合内至少有一个数字

其二，集合内的所有数字都要大于等于 1 小于等于 n

其三，集合内所有数字不能相邻。两个数字相差为一称为相邻。

由于答案很大，输出答案模 1,000,000,007 的余数。

输入格式

单个整数表示 n

输出格式

单个整数表示答案。

5

12

15

1596

数据规模与约定

30% 的数据，1 ≤ n ≤ 20

80% 的数据，1 ≤ n ≤ 2,000,000

100% 的数据，1 ≤ n ≤ 2,000,000,000