Paiza 君の階段登り 1 C編（paizaランク B 相当）

Paiza 君は段数が N の階段を上りきる必要があります。
今、Paiza 君は階段の 0 段目にいてこの階段の N 段目まで上ろうとしています。
Paiza 君は上る先の段が存在するなら階段を 1 段上るか 2 段上ることが出来ます。
N 段目まで上る方法は何通りありますか。
ただし、答えは非常に大きい数となることがあるので 10^10 で割ったあまりを出力してください。

・漸化式の立て方に関するヒント
dp[i] を階段の i 段目に上る方法の数として漸化式を考えてみてください。

・あまりの取り方に関するヒント
非負整数 A, B があります。A, B を X で割ったあまりをそれぞれ A % X, B % X として表記します。
実は (A + B) % X は ((A % X) + (B % X)) % X と同じ結果になります。
つまり、この問題では足し算をするたびに X で割ったあまりをとっても最終的な答えは変わりません。