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

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

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

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

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