In the Recursive Staircase Problem, your task is to find the number of ways of climbing a staircase of n stairs, with a set s possible steps. The example below shows that if n was 2 and s was [ 1, 2 ], the answer would be 2:

       _
   _ |2  You could either go from step 0-2 (because the set s contains 2), or
_ | 1    you could go from 0-1-2 (because the set s contains 1, taking one step at a time).
0

More examples below.

Examples

num_ways(4, [ 1, 2 ]) ➞ 5

num_ways(3, [ 1, 2, 3 ]) ➞ 4

num_ways(10, [ 1, 2, 3, 4 ]) ➞ 401

Notes

The more efficient your solution the better. Do not use unecessary recursion as this will mean the program needs far longer to complete the tests.