題目連結：
題目大意：
某一官員參加某次議會的可能情形有「出席」、「請假」、「請人代理」。
現給定一正整數 Ｎ （ ２ ≦ Ｎ ≦ １２０, ０００ ），代表某一官員要參加 Ｎ 次會議。而會議長希望這Ｎ次的會議，不要有兩次以上（含）的請假紀錄或是有連續三次（含）的請人代理。
以上，求所有可能的方法數，並將結果取 100000007 的餘數。
範例輸入：
範例輸入一：
2
範例輸入二：
3
範例輸出：
範例輸出一：
8
範例輸出二：
19
解題思維：
典型的ＤＰ（動態規劃）題。
首先，我們可以把所有合法的出勤狀況分成以下六種：
１．沒請過假，且目前最新幾次的出席為連續 ０ 次請人代理。
２．沒請過假，且目前最新幾次的出席為連續 １ 次請人代理。
３．沒請過假，且目前最新幾次的出席為連續 ２ 次請人代理。
４．請過 １ 次假，且目前最新幾次的出席為連續 ０ 次請人代理。
５．請過 １ 次假，且目前最新幾次的出席為連續 １ 次請人代理。
６．請過 １ 次假，且目前最新幾次的出席為連續 ２ 次請人代理。
再定義 Ｄ（ｉ, ｊ），代表 ｉ 次會議裡，出勤狀況為 ｊ （以上六種）的方法數。我們便可以發現：
Ｄ（ｉ, ０） ＝ Ｄ（ｉ － １, ０） ＋ Ｄ（ｉ － １, １）＋ Ｄ （ｉ － １, ２）
Ｄ（ｉ, １） ＝ Ｄ（ｉ － １, ０）
Ｄ（ｉ, ２） ＝ Ｄ（ｉ － １, １）
Ｄ（ｉ, ３） ＝ Ｄ（ｉ － １, ３） ＋ Ｄ（ｉ － １, ４）＋ Ｄ （ｉ － １, ５）＋Ｄ（ｉ － １, ０） ＋ Ｄ（ｉ － １, １）＋ Ｄ （ｉ － １, ２）
Ｄ（ｉ, ４） ＝ Ｄ（ｉ － １, ３）
Ｄ（ｉ, ５） ＝ Ｄ（ｉ － １, ４）
則ｉ次會議中，合法的方法數即是
Ｄ（ｉ, ０）＋Ｄ（ｉ, １）＋Ｄ（ｉ, ２）＋Ｄ（ｉ, ３）＋Ｄ（ｉ, ４）＋Ｄ（ｉ, ５）
最後在每次運算的時候取一次 100000007 的餘數就可以了。
