題目如下：

如果一個(gè)二進(jìn)制數(shù)包含連續(xù)的兩個(gè)1，我們就稱這個(gè)二進(jìn)制數(shù)是非法的。

找出在所有 n 位二進(jìn)制數(shù)（一共有2^n個(gè)）中，非法二進(jìn)制數(shù)有多少個(gè)。

例如對(duì)于 n = 3,有 011, 110, 111 三個(gè)非法二進(jìn)制數(shù)。

由于結(jié)果可能很大，你只需要輸出模10^9+7的余數(shù)。

輸入 一個(gè)整數(shù) n (1 ≤ n ≤ 100)。

輸出 n 位非法二進(jìn)制數(shù)的數(shù)目模10^9+7的余數(shù)。

樣例輸入：3

樣例輸出：3

解題思路： 這一題很容易讓人不知所措。。。讓我們來合理分析，抽象一下問題。問題結(jié)果抽象為S（n），即在n位內(nèi)，存在多少非法二進(jìn)制數(shù)。由于二進(jìn)制位只有1，0兩種結(jié)果，并目前數(shù)據(jù)規(guī)模假設(shè)為n，那么內(nèi)部問題結(jié)果抽象為B（n，1）與B（n，0），即在第n位為1或0時(shí)n位內(nèi)，存在多少非法二進(jìn)制數(shù)。從而理性得出，S（n）=B（n，1）+B（n，0）。

繼續(xù)分析，B（n，1）如何得出？試想一下，第n位為1時(shí)，如何保證其為非法二進(jìn)制呢？很簡(jiǎn)單，n-1位為1時(shí)，肯定保證了兩位連續(xù)的1存在。因此所有n-1位為1的數(shù)在這情況下都是非法二進(jìn)制，我們抽象結(jié)果為A（n-1），意為在n-1位內(nèi)第n-1位為1的所有二進(jìn)制數(shù)個(gè)數(shù)。那么n-1位為0時(shí)呢？這不難得出相等于B（n-1，0）的結(jié)果吧。因此得出等式B（n，1）=B（n-1，0）+A（n-1）。

然而，相比于B（n，1），B（n，0）顯得容易許多，稍微推導(dǎo)即得B（n，0）=B（n-1，1）+B（n-1，0）。

最后，A（n）又如何得出呢？我們來總結(jié)一下規(guī)律，假設(shè)n=2，A（2）即從10到11的個(gè)數(shù)，因此為（2^0 + 2^1）-2^1+1=2。n=3時(shí)，A（3）為100到111的個(gè)數(shù)，即（2^2+2^1+2^0）-2^2+1=4。n=4時(shí)，A（4）為1000到1111的個(gè)數(shù)，即（2^3+2^2+2^1+2^0）-2^3+1=8。好了，從以上式子得出A（n）=A（n-1）+2^(n-1)。

綜合上述，我們得出了以下一系列方程： S（n）=B（n，1）+B（n，0） B（n，1）=B（n-1，0）+A（n-1） B（n，0）=B（n-1，1）+B（n-1，0） A（n）=A（n-1）+2^(n-1)

從方程可以看出，n規(guī)模數(shù)據(jù)結(jié)果是由n-1規(guī)模數(shù)據(jù)得出，因此從低到n規(guī)模遞推數(shù)據(jù)結(jié)果即可解決。

思路代碼實(shí)現(xiàn)如下：