根據民主政治的精神，政府單位有責任到民意代表所組成的會議中接受質詢與監督。某議會的議長在會期開始前就和政府單位進行下面的溝通：「我們議會希望被質詢的官員每一次都要出席。如果有兩次以上的請假紀錄，或是連續三次以上請代理的同仁來接受質詢的話，恐怕會造成雙方溝通上的緊張。」
請你寫一隻程式來統計一下，當官員需要被質詢 N 次的情況下，有多少種官員出席紀錄可以保持府會的和諧關係。另外，由於答案可能會非常大，請回傳除以 100000007 之後的餘數。
測試資料只有一行，只有一個正整數 N，代表某一官員所要接受質詢的次數。N 的範圍從 2 到 120000。
輸出資料為一個數值，為能夠保持府會和諧的出席紀錄組合數量。
範例輸入一： 2 範例輸入二： 3
範例輸出一： 8 範例輸出二： 19
範例輸入一：
八種組合列在下面：
[出席，出席][出席，代理][代理，出席]
[請假，出席][請假，代理][出席，請假]
[代理，請假][代理，代理]
範例輸入二：
會破壞行政單位和議會關係的紀錄組合：
[假假出][假出假][出假假][假假代][假代假]
[代假假][假假假][代代代]