2009：非法二进制数
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：4
解决：3
题目描述
如果一个二进制数包含连续的两个 $1$，我们就称这个二进制数是非法的。小爱想知道在所有的 $n$ 位二进制数（一共有 $2^n$ 个）中，非法二进制数有多少个？
例如对于 $n=3$，有 $011,110,111$ 三个非法二进制数。
由于结果可能很大，你只需要输出模 $10^9+7$ 的余数。
输入
一个整数 $n(1\le n\le 100)$
输出
$n$ 位非法二进制数的数目模 $10^9+7$ 的余数。
样例输入-1 复制
3样例输出-1 复制
3