Paiza 君の階段登り 3 Python2編（paizaランク S 相当）

段数が N の階段があります。
今、魔法の杖を持った Paiza 君が階段の 0 段目にいてこの階段の N 段目まで上ろうとしています。
魔法の杖には M 種類の魔法が込められており、それぞれ a_1, a_2, ..., a_M で表されます。
i (1 ≦ i ≦ M) 番目の魔法を使うと a_i 段上が存在するならば a_i 段上に移動することが出来ます。
しかし、それぞれの魔法は一度きりしか使うことが出来ません。

Paiza 君は 2 通りの行動を取ることが出来ます。
・階段を 1 段上に上る。
・i 番目の魔法を使う。その後、i 番目の魔法は二度と使うことが出来なくなる。

N 段目までの上り方は何通りありますか。このとき、上る段数が同じであっても移動手段が異なる場合は別の上り方としてカウントしてください。