答案:

設F(n)表示走到第n格的方法數則F(1)=1,F(2)=2

F(n+2)=F(n+1)+F(n),n>=1

因為有兩種方法能到第n+2格，要嘛是從n+1格跨一格上，要嘛從第n格跨兩步上來，然後加起來

然後實作時最常見的是遞迴法不過可能會遞迴到overflow

所以可以開一個陣列把已經算過的存起來(因為同餘有加法性所以模之後再加答案也是對的)，用一點空間換取極大的效率

有點類似DP的概念(?，希望能幫助到大家