Responsive image

问题 1925 --非法二进制【多组实例测试】

1925: 非法二进制【多组实例测试】

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

如果一个二进制数包含连续的两个1，我们就称这个二进制数是非法的。

小Hi想知道在所有 n 位二进制数（一共有2^n个）中，非法二进制数有多少个。

例如对于 n = 3,有 011, 110, 111 三个非法二进制数。

由于结果可能很大，你只需要输出模10^9+7的余数。

输入描述

一个整数 n (1 <= n <= 100)。

输出描述

n 位非法二进制数的数目模10^9+7的余数。

样例输入

3

样例输出

3

来源

2017 计算机学院软件学院推广赛 

[提交][状态]
ACM算法攻关部