電石──並非拋入水中會產生乙炔的那樣東西，而是一個人的稱號──在見到東東的事蹟後心生嚮往，決定朝成為爬樓梯大師的目標邁進。

曾幾何時，電石已然爬過八百萬階樓梯，他參加國際爬樓梯大賽並勇奪世界冠軍，一時間名滿天下，眾人聽聞消息無不欣慕。

然而在漫長的磨練中，電石發掘出一項隱藏在腳底下的神秘性質：

若每步只能向上走一階或二階，且總共有 $n$ 階樓梯，則 $n=1$ 時有一種走法，$n=2$ 時有兩種，把 $n=1,2,3,4,5,6,7,8,9,10,\cdots$ 的走法數寫下來會是 $1,2,3,5,8,13,21,34,55,89,\cdots$。

然後把每個數都改成除以二的餘數，即 $1,0,1,1,0,1,1,0,1,1,\cdots$，可以觀察到數字以 $1,0,1$ 的形式重複出現。電石發現無論除以多少，走法數的餘數似乎都會循環，他現在正忙著爬樓梯，所以請你撰寫程式幫忙驗證。