Problem : 173 - 選座位

Problem Statistics

Solved Member: 29　　Submission: 67　　User Tried: 29

Statement:

在天龍國裡，人們是很害羞的。天龍國大眾運輸系統的座位是呈一字排開，而人們總是不好意思緊鄰人而座。在有三個座位時，所有五種可能的座位情形如下圖所示。空心圓圈代表無人的座位、實心圓圈代表有人的座位，那麼根據天龍人們的獨特默契，意謂著不可能發生兩個實心圓圈相鄰這種情形。

對於n個一字排開的座位，有多少種不同的可能性呢？
最後你發現這個問題的答案和某個惡名昭彰的數列有關(是什麼這裡就不提了)

真正的問題和這個很類似，只不過這次是大龍國的大眾運輸系統。
在大龍國裡，人們真的很大方很大方、他們選座位的時候喜歡緊鄰人而座！這樣才能和盡可能多的陌生人聊天、分享城市生活的喜悅。可是也正因為這樣，年久失修的大龍國捷運，有著座位會壞掉的問題(太擠了)：

「如果連續三個人或以上坐在一起，中間的位子就會垮掉！(白色叉叉)」

請問：對於n個一字排開的座位，每個位子只有兩種可能：有人坐或沒有人坐。只要連續三個人或三個人以上坐在一起，座位就會垮掉。在不讓座位垮掉的前提下，有多少種可能的座位情形呢？

另外，其實大龍國官方已經外包請工讀生寫出了這支程式，為求驗證程式結果的正確性，你被要求輸出答案除以10000019的餘數就可以了。

Input:Output:

每個測試檔僅有一筆測試資料。
唯一的一行包含一個正整數n，代表有n個座位一字排開
其中n≦100000

輸出唯一的一行，包含一個整數，表示n個座位時有多少種可能的情形
由於答案可能非常大，請輸出答案除以10000019的餘數

Sample Input:Sample Output:

Sample 1
3

Sample 2
4

Sample 1
7

Sample 2
13

Source:

101附中校內賽

Problem Setter

lajisongyy_jack1

Testdata:

Test	Time	Memory	Score
0-1	2000ms	65536kb
0-2	2000ms	65536kb
1	2000ms	65536kb	20
2	2000ms	65536kb	20
3	2000ms	65536kb	20
4	2000ms	65536kb	20
5	2000ms	65536kb	20